[백준] 2178번 파이썬 - BFS 풀이

문제 요약 (2178.  미로 탐색)

n * m 크기의 배열로 표현되는 미로가 주어질 때, (1, 1) 부터 (n, m)으로 이동하기 위해 지나가야하는 칸 수의 최솟값을 구해 출력한다.

배열의 n, m 모두 100 이하이기 때문에 시간 복잡도는 걱정할 필요는 없다.

2178번: 미로 탐색

 

풀이를 위한 부연 설명

• 길찾기를 위한 표의 경우 45도 꺽어서 보면 그래프로 표현할 수 있다.
  • 그래프의 문제의 경우 DFS와 BFS를 이용한 풀이 두 가지 모두 생각할 수 있다
• 그러나 해당 문제는 BFS를 통해 문제를 풀어야한다
  • 완전 탐색을 진행하여 언제 원하는 값을 구하는지 찾아야하는 것이다.
  • BFS는 깊이 내에서 갈 수 있는 노드 탐색을 모두 마치고 다음 깊이로 가기 때문에 완전성을 보장합니다.
• 길 찾기를 위해 좌표값을 이용한다.
  • x 좌표와 y 좌표의 변화량을 표시하는 dx, dy 를 만들어 체크한다.
  • 또한 변화된 좌표가 유효한 값인지도 확인하는 절차가 필요하다
• BFS 문제 이므로 큐를 이용하여 문제를 풀어야한다.

• BFS에 대한 개념과 연관 문제는 다음 게시글을 참고하면 된다.

[코테 알고리즘] DFS, BFS / 관련 문제

 

코드

from collections import deque

n, m = map(int, input().split())
maze = [[0] * m for _ in range(n)]
checked = [[False] * m for _ in range(n)]

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


for i in range(n):
    kk = list(input())
    for j in range(m):
        maze[i][j] = int(kk[j])

que = deque()
que.append((0, 0))
checked[0][0] = True

while que:
    new = que.popleft()
    for k in range(4):
        x = new[0] + dx[k]
        y = new[1] + dy[k]
        if x >= 0 and y >= 0 and x < n and y < m:
            if maze[x][y] != 0 and not checked[x][y]:
                checked[x][y] = True
                maze[x][y] = maze[new[0]][new[1]] + 1
                que.append((x, y))

print(maze[n-1][m-1])

 

 

기억할 점

• 먼저 미로를 그래프로 표현하고, DFS와 BFS 중 어떤 방법으로 풀어야하는지 고민을 해야한다.
• 좌표 변화 표현을 위하여 dx, dy를 이용한다.