PS/Baekjoon Online Judge
[백준 02178] 미로 탐색 [Python]
kimyoungrok
2025. 2. 26. 14:02
728x90
문제
https://www.acmicpc.net/problem/2178
풀이
주어진 보드의 (0, 0)에서 (N - 1, M - 1)에 도달하기 위해 움직인 최소 횟수를 구하는 문제다.
BFS로 탐색을 진행했다.
if __name__ == '__main__':
# Input
N, M = map(int, input().split())
board = [[*map(int, input().rstrip())] for _ in range(N)]
# Solve & Output
print(bfs(N - 1, M - 1))
큐에는 현재 위치 (x, y)를 담았으며, 따로 방문 횟수를 기록해도 되지만 주어진 board를 활용했다.
빈 공간은 1로, 이동하면서 기존 위치의 값 + 1으로 채웠다.
이미 방문한 곳은 1이 아니여야 하기 때문에 (0, 0)을 2로 시작했고,
마지막 결과에서 다시 1을 빼주는 방식으로 올바른 정답을 계산했다.
def bfs(N, M):
queue = deque([(0, 0)])
board[0][0] = 2
while queue:
x, y = queue.popleft()
if x == N and y == M:
return board[x][y] - 1
for dx, dy in D:
nx, ny = x + dx, y + dy
if is_valid(nx, ny):
board[nx][ny] = board[x][y] + 1
queue.append((nx, ny))
소스코드
https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/02178.py
728x90