백준 1261
알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 구하기.
- 알고스팟 운영진이 모두 미로에 갇혔다. 미로는 NxM 크기이며, 총 1x1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.
- 알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다.
- 벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으로 변한다.
- 현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.
- 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다.
- (1, 1)과 (N, M)은 항상 뚫려있다.
입출력
| 입력 | 출력 |
|---|---|
| 3 3 011 111 110 | 3 |
| 4 2 0001 1000 | 0 |
| 6 6 001111 010000 001111 110001 011010 100010 | 2 |
접근 방식
: 상하좌우 탐색 시 0이면 우선순위에 앞서기 위해 appendleft. 1이면 append.
이 때 1이면 벽을 부수는 것이므로 1을 더해서 visited에 기록
알게된 점
우선순위 큐(힙) 자료구조를 이용할 수 있다.
코드
덱을 이용한 풀이
from collections import deque
import sys
def bfs(maps, visited, n, m):
visited[0][0] = 0
q = deque()
q.append((0,0))
dx = [-1,1,0,0]
dy = [0,0,-1,1]
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<n and 0<=ny<m:
if visited[nx][ny] == -1 :
if maps[nx][ny] == 0:
visited[nx][ny] = visited[x][y]
q.appendleft((nx, ny))
else:
visited[nx][ny] = visited[x][y] + 1
q.append((nx, ny))
return visited[-1][-1]
m, n = map(int, sys.stdin.readline().split())
maps = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(n)]
visited = [[-1]*m for _ in range(n)]
print(bfs(maps, visited, n, m))힙을 이용한 풀이
import heapq
import sys
def bfs():
q = []
heapq.heappush(q, [0, 0, 0])
visited[0][0] = 1
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
while q:
w, x, y = heapq.heappop(q)
if x==n-1 and y==m-1:
return w
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<n and 0<=ny<m and visited[nx][ny] == 0:
heapq.heappush(q, (w+1 if maze[nx][ny] == 1 else w, nx, ny))
visited[nx][ny] = 1
m, n = map(int, sys.stdin.readline().split())
maze = [list(map(int, sys.stdin.readline().rstrip('\n'))) for _ in range(n)]
visited = [[0]*m for _ in range(n)]
print(bfs())