[백준 알고리즘/Python] 2178 미로 탐색

문제

 

문제 이해

처음에 dfs로 풀려다가 뭔가 이상한거 같아서 더 좋은 방법이 있겠다 생각했습니다. 가까이 있던 bfs를 생각해보았습니다.

bfs로 <1,1>에서 부터 1칸씩 쭉쭉 이동할 때 마다 count를 1씩 늘려주면 됩니다.

그렇다면 1번 씩 이동할 때 마다 count를 1개씩 늘려줘야 하니 queue 안에 다음 좌표값과 이동해온 크기를 집어넣습니다. 큐에 넣을때마다 크기를 증가시키는게 아니라 한 사이클마다 크기를 증가시켜줘야 합니다.

 

여기서 사이클은 어떤 좌표에 있을 때 주변에 1이 있다면 그곳으로 가야할 것입니다. 

ex) <2,2,3>라는 좌표가 있습니다. <2,2>까지 오는데 3번 걸린 것입니다. 만약 <2,3>으로 가야한다면 <2,3,4>를 큐에 집어넣으면 됩니다. 만약에 <1,3>에도 1이 있습니다. 그러면 <1,3,4>를 큐에 집어넣습니다.

 

이런식으로 큐에 집어넣으면 해당 좌표에 도착했을 때 큐의 마지막값을 출력하면 됩니다.

 

코드

from collections import deque
import sys
sys.setrecursionlimit(10**6)

w, h  = map(int,input().split())

#2차원 배열 만들기
graph = []
for i in range(w):
    graph.append(list(map(int,input())))

def check_round(x,y):
    if(x <= -1 or x >= w or y <= -1 or y >= h): #범위 밖으로 나가면
        return False
    else:
        return True

#BFS 메서드 정의
def bfs(result_x,result_y):
    #큐 구현을 위해 deque 사용
    queue = deque([[0,0,0]])
    #현재 노드를 방문 처리
    graph[0][0] = 0
    #큐가 빌때 까지 반복
    while queue:
        #큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        x = v[0]
        y = v[1]
        count = v[2]

        #목적지에 오면 동작
        if(x == result_x-1 and y == result_y-1):
            print(count+1)
            break

        if (check_round(x+1,y) ): #하
            if(graph[x+1][y] == 1):
                queue.append([x+1, y ,count+1])
                graph[x+1][y] = 0

        if (check_round(x,y+1)): #우
            if(graph[x][y+1] == 1 ):
                queue.append([x, y+1 ,count+1])
                graph[x][y+1] = 0

        if (check_round(x-1,y) ): #상
            if(graph[x-1][y] == 1):
                queue.append([x-1, y ,count+1])
                graph[x-1][y] = 0

        if (check_round(x,y-1)): # 좌
            if(graph[x][y-1] == 1 ):
                queue.append([x, y-1 ,count+1])
                graph[x][y-1] = 0

#정의된 bFS 함수 호출
bfs(w,h)

x,y가 목표지점에 도달했을 때 count는 1적습니다. 왜냐하면 0부터 탐색했기 때문입니다.