Swea D3_11886. 미로의 거리 Python BFS

풀이 총 소요시간 : 1시간?

dr = [0,1,0,-1]
dc = [1,0,-1,0]

def find_start(arr):
    for i in range(N):
        for j in range(N):
            if arr[i][j] ==2:
                r,c = i,j
                return r,c # local
def maze_go(r,c):
    global flag
    q = [(r,c)]
    visited[r][c] = 1
    while q:
        r,c = q.pop(0)
        for k in range(4):
            nr = r + dr[k] # 4방향으로 갈 행
            nc = c + dc[k] # 4방향으로 갈 열
            if 0 <= nr < N and 0 <= nc < N and visited[nr][nc] == 0:
                if maze_arr[nr][nc] == 0:
                    maze_arr[nr][nc] = 9 # 방문했다
                    q.append((nr,nc))
                    visited[nr][nc] = visited[r][c] + 1
                if maze_arr[nr][nc] == 3:
                    return visited[r][c]-1
    return 0
T = int(input())
for tc in range(1,T+1):
    N = int(input()) # N 미로의 한 변 크기
    maze_arr = [list(map(int,input())) for _ in range(N)]
    visited = [[0] * N for _ in range(N)]
    r, c = find_start(maze_arr) # global
    print(f'#{tc} {maze_go(r,c)}')

실수한 부분

1. BFS를 배웠기 때문에 Queue로 푸는 것이 정석에 가까운데

stack을 쓰지 않는 DFS 로 풀려고 했었다. (= 말이 안됨)

길을 잘못 들 경우 다시 돌아오는 코드를 구현하지 않았기 때문에, 갈수있음에도 불구하고 가지못한다고 출력됐음

2. Queue를 사용하고 나서

3에 도착했을 때 결과를 return 한다

if maze_arr[nr][nc] == 3:
    return visited[r][c]-1

하지만, visited[nr][nc]-1 로 두게 되면서 방문 체크 하지 않은 (도착하지 않은) 좌표의 값을 return 했기 때문에 0이 나올수 밖에 없었음