[백준] 2178 미로 탐색 (실버1) / BFS

문제요약

나의 코드 및 설명

from collections import deque

def bfs(sx,sy,ex,ey): #시작(x,y)좌표, 종료(x,y)좌표
    queue = deque()
    queue.append((sx,sy)) #먼저 시작좌표를 큐에 삽입
    visited[sy][sx] = 1 #시작좌표 방문처리
    while queue: #큐가 빌때까지
        x,y = queue.popleft() #첫 번째 케이스: 처음에 넣은 시작 좌표를 꺼낸다. / 나머지 케이스: ->반복
        if (x,y) == (ex,ey): #큐가 빌때까지 돌았는데 시작좌표가 종료좌표와 일치할 때
            return visited[ey][ex] #종료좌표에 해당되는 방문리스트에 저장된 값 리턴
        for i in range(4): #동서남북 네 방향 돈다.
            nx = x+dx[i]
            ny = y+dy[i]
            if nx<0 or ny<0 or nx>=m or ny>=n: #미로 밖으로 벗어날 경우 다음 방향 실행
                continue
            else:
                if board[ny][nx] == 1 and visited[ny][nx] == 0: #갈 수 있고, 방문 안되어 있다면
                    queue.append((nx,ny)) #일단 큐에 다음좌표 넣고
                    board[ny][nx] = 0 #다음좌표 못간다 표시하고
                    visited[ny][nx] = visited[y][x] + 1 #다음좌표 방문리스트에 현재좌표+1을 저장한다.
        ##pop한 하나의 좌표에 대한 길에대한 모든 정보를 큐에 집어넣었으므로
        ##이제 다시 돌아가서 큐에 좌표를 하나씩 pop하면서 갈 수 있는지 없는지 살펴보면 된다.

n,m = map(int, input().split())
board = []
for _ in range(n):
    board.append(list(map(int, str(input()))))
dx = [0,1,0,-1]
dy = [1,0,-1,0]

visited = [[0]*m for _ in range(n)]
print(bfs(0,0,m-1,n-1))

피드백

최단거리 문제는 BFS로 푸는 것이 일반적이고, visited 리스트 등 룩업 테이블에 이동할 때의 정보를 하나하나 기록 하면서 종료 좌표에 도달했을 때 룩업 테이블의 종료좌표에 해당되는 인덱스에 저장된 값을 리턴하는 식으로 문제를 해결한다는 것을 학습할 수 있었다.