문제
문제 : https://www.acmicpc.net/problem/2178
N X M 크기의 배열로 표현되는 미로가 있다.
| 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 |
미로에서 1은 이동할 수 있는 칸이고, 0은 이동할 수 없는 칸이다. 이 미로에서 (1, 1)에서 출발해 (N, M)으로 이동할 때 지나야 하는 최소 칸의 개수를 구하는 프로그램을 작성하라. 한 칸에서 다른 칸으로 이동할 때는 서로 인접한 칸으로만 갈 수 있다.
입력의 첫째 줄에는 두 정수 N, M이 주어지고, 다음 N개의 줄에 M개의 정수가 붙어서 입력으로 주어진다. 또한 항상 도착 위치로 이동할 수 있는 경우만 고려한다.
2024.05.10-[프로그래머스] 게임 맵 최단거리와 동일한 형태의 BFS 문제이다. 게임 맵 최단거리에서 불필요한 중복 코드를 줄이면 좋겠다고 적어두었는데 이번 글에서 복습할 겸, 코드 개선도 할 겸 풀어보려고 한다.
풀이
1. 값 초기화
방문 여부와 해당 지점을 가기 위해 지나가야 하는 칸의 수를 저장할 visited을 선언하고 초기화한다. 또한 칸 이동과 관련된 정보인 directions를 선언한다.
visited = [[0 for _ in range(m)] for _ in range(n)]
directions = [(1, 0), (0, -1), (-1, 0), (0, 1)]
2. 시작점 방문
큐에 시작 칸을 추가하고, 방문 여부를 업데이트한다.
queue = [start]
visited[start[0]][start[1]] = 1
3. 큐가 빌 때까지 아래 과정을 반복한다.
- 큐에서 방문한 위치를 꺼낸다.
i, j = queue.pop(0)
- 다음에 방문하는 칸의 위치를 확인하고 방문한 칸의 위치는 큐에 넣는다.
for x, y in directions:
ni, ny = i + x, j + y
if 0 <= ni < n and 0 <= ny < m and maps[ni][ny] == 1:
if visited[ni][ny] == 0:
queue.append((ni, ny))
visited[ni][ny] = visited[i][j] + 1기존 소스에서 이 부분을 수정했다. 방문할 칸의 위치를 확인할 때 행과 열의 인덱스, 방문 가능 여부, 방문 여부를 한 번에 확인한다.
그리고 DFS와 관련된 부분을 함수로 분리해 보았다.
def bfs(maps, n, m, start=(0, 0)):
visited = [[0 for _ in range(m)] for _ in range(n)]
directions = [(1, 0), (0, -1), (-1, 0), (0, 1)]
queue = [start]
visited[start[0]][start[1]] = 1
while queue:
i, j = queue.pop(0)
for x, y in directions:
ni, ny = i + x, j + y
if 0 <= ni < n and 0 <= ny < m and maps[ni][ny] == 1:
if visited[ni][ny] == 0:
queue.append((ni, ny))
visited[ni][ny] = visited[i][j] + 1
return visited
3. 입력값 초기화 및 출력
입력받은 값을 bfs 함수에 전달하여 실행한다. visited를 반환받으므로 행이 n - 1이고 열이 m - 1인 칸의 값을 출력하면 된다.
n, m = map(int, sys.stdin.readline().split())
maze = [list(map(int, list(sys.stdin.readline().strip()))) for _ in range(n)]
bfs = bfs(maze, n, m)
print(bfs[n - 1][m - 1])
참고 문서
https://www.acmicpc.net/problem/2178