[SWEA] - 5105. 미로의 거리

swea - 문제 링크

from collections import deque

def bfs(r, c):
    global result
    Q.append([r, c])
    visit_level[r][c] = 1
    # Q가 비어있을때까지
    while Q:
        # 현재위치 큐에서 뽑아오기
        temp = Q.popleft()
        # 4방향탐색
        for i in range(4):
            nr = temp[0] + dx[i]
            nc = temp[1] + dy[i]
            # 범위체크
            if 0 <= nr < N and 0 <= nc < N:
            	# 길이 있고 방문하지 않았다면
                if maze[nr][nc] != '1' and visit_level[nr][nc] == 0:
                    #방문거리를 기록
                    visit_level[nr][nc] = visit_level[temp[0]][temp[1]] + 1
                    # 도착지점이라면
                    if maze[nr][nc] == '3':
                        # 처음 visit_level이 1 이었고 마지막 도착했을때 더해준 값해서 총 2 빼주기
                        result = visit_level[nr][nc] -2
                        return result
                    Q.append([nr, nc])
    return result

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

for tc in range(1, int(input()) + 1):
    N = int(input())
    maze = [list(input()) for _ in range(N)]
    # 방문을 안했다면 0, 방문을 했다면 그 숫자는 거리(level)
    visit_level = [[0] * N for _ in range(N)]
    Q = deque()
    result = 0

    for x in range(N):
        for y in range(N):
            if maze[x][y] == '2':
                sr, sc = x, y

    print('#{} {}'.format(tc, bfs(sr, sc)))

🔑 포인트는 visit_level을 잘 설정해주는 것!
visit_level[nr][nc] = visit_level[temp[0]][temp[1]] + 1 -> 내가 도착한 지점은 도착하기 직전의 곳에서 1칸만큼 더 온 곳이기 때문에 따로 방문처리와 거리기록을 하지 않고 한꺼번에 했다. 어차피 방문하지 않았다면 0일것이기 때문에!
그래서 내가 Q에서 뽑은 temp가 행과 열로 구성된 리스트이기 때문에 temp[0] 과 temp[1]을 방문기록의 행과 열에 써주었다.
BFS가 어렵게 느껴진다면 이 문제는 어려운 문제이지만, BFS를 한번 이해하고 나니 이정도는 기초문제인것이 느껴진다,,,😓