BOJ 2178 미로 탐색

태그

그래프 이론

그래프 탐색

너비 우선 탐색

생성일

2024/12/11 12:13

URL

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

문제 설명

•

행렬(2차원 배열)이 주어졌을 때, (1,1)(1, 1)(1,1)에서 (N,M)(N, M)(N,M)까지 가는 최단 거리를 구하는 문제

◦

NNN: 세로(행)의 크기

◦

MMM: 가로(열)의 크기

예제 입력/출력

•

입력1

Plain Text
복사

•

출력1

Plain Text
복사

제약 조건

•

2≤N,M≤1002 ≤ N, M ≤ 1002≤N,M≤100

문제 풀이

•

그래프 탐색을 이용하여 문제를 해결하면 된다. - O(N⋅M)O(N \cdot M)O(N⋅M)

◦

노드의 개수가 NM개이고, 나올 수 있는 간선의 최대 개수는 4NM

◦

BFS 알고리즘을 이용

풀이 코드

from collections import deque

# Input
N, M = map(int, input().split())

maps = [[0 for _ in range(M)]]
for _ in range(N):
	maps.append([0] + list(map(int, input())))

# Init
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
visited = [[-1 for _ in range(M + 1)] for _ in range(N + 1)]

# Solve (BFS)
q = deque()
q.append((1, 1))
visited[1][1] = 1

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

	if x == M and y == N:
		break

	for i in range(4):
		nx = x + dx[i]
		ny = y + dy[i]
		if (1 <= nx <= M) and (1 <= ny <= N) and visited[ny][nx] == -1 and maps[ny][nx] == 1:
				q.append((nx, ny))
				visited[ny][nx] = visited[y][x] + 1

print(visited[N][M])
Python
복사