[백준 파이썬] # 2178 미로 탐색 (BFS 풀이)

Silver I

# 2178 미로탐색 (BFS 풀이)

링크 : https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

풀이 (BFS)

from collections import deque

N, M = map(int, input().split())  # M: 가로(열 인덱스), N: 세로(행 인덱스)
graph = []
for i in range(N):
    line = list(map(int, input()))
    graph.append(line)

def bfs(x, y):    
    queue = deque()
    queue.append((x,y))

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

    while queue:
        x, y = queue.popleft()

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

            if 0<=nx<M and 0<=ny<N:
                if graph[ny][nx] == 1:
                    queue.append((nx, ny))
                    graph[ny][nx] = graph[y][x] + 1  # key_idea

    return graph[N-1][M-1]  #key_idea

print(bfs(0,0))

 

풀이 과정

• (0, 0) 에서 (N, M) 이동할 때까지 거치는 1의 개수를 출력하는 문제다
• 시작점으로 부터 상하좌우 네 방향을 탐색하고, 1이 있을 경우 다시 탐색을 반복하는 구조이기 때문에 BFS 풀이 적용이 가능하다
• 이전에 사용했던 visited 행렬을 체커로 사용하는 방식보다 while문이 몇번 반복했는지를 체커로 사용하는 방법이 더 좋다

 

후기

• 온전히 내 힘으로 푼 것은 아니고 치팅을 조금 활용..
• 설계를 어떻게 하는가에 따라 코드가 복잡해지기도, 간단해지기도 하는 것 같다
• 쉬운 BFS 풀이를 위해 체커를 어떻게 활용할지에 대해 고민을 좀더 해봐야 할듯
• bfs 구조 보다는 정답을 출력하는 과정에서 꽤 애를 먹는 듯 하다