[백준/BOJ] - 1987번 python 풀이 - DFS

---

Key Point

1. dfs 알고리즘에 대해 정확히 아는지 여부가 중요한 문제이다.

2. (0,0) 위치에서 시작하여 동서남북으로 갈 수 있는 방향으로 진행하며 진행 1회당 cnt를 1 증가시킨다.

3. 이동했을 경우 이동한 알파벳을 visited set에 저장시킨다.

4. golbal value인 ans와 cnt를 비교하며 계속 max 값을 갱신한다.

5. 끝에 도달했을 때의 max 값이 정답 max 값이 아니더라도 재귀 함수 특성상 이전 함수로 이동하여 cnt를 증가시킨 부분이 무효화 되고 그 노드에서 동서남북으로 갈 수 있는 위치를 찾아 진행한다.

6. 맨 처음 선택한 방향이 정답 max 값이 아니더라도 모든 경로를 탐색하는 dfs 특성상 찾을 수 밖에 없는 구조이다.

7. 다만 알아야 할 점은 하나의 dfs 함수가 끝날 경우 visited set에서 해당 노드를 삭제시켜 주어야한다.

 

알게 된 점

visited = set()
graph = [1,2,3]

visited.add(graph[0])) # (1)
visited.remove(graph[0]) #(0)

visited 함수를 set 형식으로 선언하여 add, remove를 통해 기록할 수 있다.

---

r, c = map(int, input().split())
graph = [list(input()) for _ in range(r)]
visited = set()
dx, dy = (-1, 1, 0, 0), (0, 0, -1, 1)
ans = 0


def dfs(x, y, cnt):
    global ans

    ans = max(ans, cnt)
    visited.add(graph[x][y])

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]

        if 0 <= nx < r and 0 <= ny < c:
            if graph[nx][ny] not in visited:
                dfs(nx, ny, cnt + 1)

    # 동서남북 가려 했는데 갈 곳이 없으면 dfs 끝나면서 방문 함수에서 제거
    # 이전에 dfs 호출 했던 곳으로 이동 하면서 cnt+1 했던거 무효 된다.
    visited.remove(graph[x][y])


dfs(0, 0, 1)

print(ans)