📚문제: #1261 알고스팟(Gold 4)
알고스팟 운영진이 모두 미로에 갇혔다. 미로는 NxM 크기이며, 총 1x1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.
알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.
벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으로 변한다.
만약 이 문제가 알고스팟에 있다면, 운영진들은 궁극의 무기 sudo를 이용해 벽을 한 번에 다 없애버릴 수 있지만, 안타깝게도 이 문제는 Baekjoon Online Judge에 수록되어 있기 때문에, sudo를 사용할 수 없다.
현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다.
(1, 1)과 (N, M)은 항상 뚫려있다.
출력
첫째 줄에 알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.
예제 입력
6 6
001111
010000
001111
110001
011010
100010예제 출력
2아이디어 및 구현
- 미로의 [0,0]에서 [N-1,M-1]로 이동할 때 우선순위 큐를 활용한다. 이 때 우선순위 큐 내부는 벽을 부순 횟수를 기준으로 정렬된다.
...(중략)...
# 시작지점 초기화 (벽 수, 시작지점), # start = [0,0]
heappush(q, (0, start))
# 현재 지점에서 이동가능한 지점을 살펴본다.
for i in range(4):
move_r = cur_r + dr[i]
move_c = cur_c + dc[i]
# 주어진 범위를 벗어나지 않으면서
if 0 <= move_r <= N-1 and 0 <= move_c <= M-1:
# 이동가능 지점이 빈 공간일 때
if maze[move_r][move_c] == 0:
# 방문처리
maze[move_r][move_c] = 'v'
heappush(q, (wall, [move_r, move_c]))
# 이동하려는 지점이 벽 일때
elif maze[move_r][move_c] == 'w':
# 방문처리
maze[move_r][move_c] = 'v'
# 벽을 1개 더 부숴야한다.
heappush(q, (wall+1, [move_r, move_c]))
# 이미 방문처리 된 지점은 skip합니다.
else:
continue
- 우선순위 큐에서 꺼낸 지점의 좌표가 [N-1,M-1]일 때, 벽을 부순 횟수를 출력하고 종료한다.(우선순위 큐 안에 [N-1,M-1] 좌표 값을 가진 여러개의 데이터 중 벽을 부순횟수가 가장 적은 데이터가 나오게된다.)
...(중략)...
wall, cur = heappop(q)
cur_r, cur_c = cur
# 마지막 지점에 도착했을 때 출력
if cur_r == N-1 and cur_c == M-1:
print(wall)
break전체 코드
import sys
from heapq import heappush, heappop
# Dijkstra Algorithm
def Dijkstra(start):
# 4방향
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
# Priority Queue
q = []
# 시작노드 초기화 (벽 수, 시작지점)
heappush(q, (0, start))
# 큐가 빌 때까지 반복합니다.
while q:
wall, cur = heappop(q)
cur_r, cur_c = cur
# 마지막 지점에 도착했을 때 출력
if cur_r == N-1 and cur_c == M-1:
print(wall)
break
for i in range(4):
move_r = cur_r + dr[i]
move_c = cur_c + dc[i]
# 주어진 범위를 벗어나지 않으면서
if 0 <= move_r <= N-1 and 0 <= move_c <= M-1:
# 이동가능 지점이 빈 공간일 때
if maze[move_r][move_c] == 0:
maze[move_r][move_c] = 'v'
heappush(q, (wall, [move_r, move_c]))
# 이동하려는 지점이 벽 일때
elif maze[move_r][move_c] == 'w':
maze[move_r][move_c] = 'v'
heappush(q, (wall+1, [move_r, move_c]))
# 방문처리 된 지점은 skip합니다.
else:
continue
# 가로크기 M, 세로크기 N이 주어집니다.
M, N = map(int, sys.stdin.readline().split())
# 미로 초기화
maze = []
# 미로의 상태가 주어집니다.
for i in range(N):
maze.append(list(sys.stdin.readline().rstrip()))
for j in range(M):
maze[i][j] = int(maze[i][j])
# 1을 벽으로 변경
for i in range(N):
for j in range(M):
if maze[i][j] == 1:
maze[i][j] = 'w'
# Dijkstra Algorithm
Dijkstra([0,0])TIL
Dijkstra 알고리즘 풀이라기 보다, BFS 알고리즘에 우선순위 큐 개념을 도입한 것으로 이해하는 게 좀 더 편한 것 같다. 일반적인 미로탐색 문제와 다른점은 【우선순위 큐】를 통해 벽을 적게 부수며 이동할 수 있는 지점부터 최우선적으로 방문한다는 부분이다. 아래는 Chat GPT에게 질문한 결과이다.
- ❓BFS에 Priority queue를 활용하는 경우를 알려줘
- 📚BFS(Breadth-First Search)를 진행할 때, 일반적으로 큐(Queue)를 사용하여 노드를 탐색 순서에 따라 저장하고 처리합니다. 그러나 BFS에 우선순위 큐(Priority Queue)를 활용하는 경우도 있습니다. 우선순위 큐를 사용하는 경우, 노드를 탐색 순서에 따라 우선순위에 따라 처리하므로 일반 큐를 사용하는 경우와 다르게 동작합니다.
우선순위 큐를 활용하는 경우, 다음과 같은 상황에서 유용할 수 있습니다:
- 최소 비용 경로 탐색: 그래프나 트리에서 최소 비용 경로를 찾아야 할 때, 각 노드의 비용을 고려하여 우선순위 큐를 사용하면 최소 비용 노드를 먼저 탐색할 수 있습니다. 이는 Dijkstra's 알고리즘과 유사한 방식으로 작동합니다.
- 휴리스틱 기반 탐색: A* 알고리즘과 같은 휴리스틱 기반의 탐색 알고리즘에서 우선순위 큐를 사용하여 더 가능성 있는 노드를 먼저 탐색할 수 있습니다. 이것은 최단 경로 문제나 인공 지능 탐색 문제에 유용합니다.
- 특정 조건을 만족하는 노드 탐색: 우선순위 큐를 사용하여 특정 조건을 만족하는 노드를 먼저 처리할 수 있습니다. 예를 들어, 특정 값 이상의 노드를 찾는 경우 우선순위 큐를 사용하여 해당 노드를 먼저 처리할 수 있습니다.
- 최적화 문제: 어떤 최적화 문제를 해결할 때, 우선순위 큐를 사용하여 현재 상태에서 가능한 최적의 선택을 먼저 탐색할 수 있습니다.
우선순위 큐를 사용하면 BFS를 수정하여 다양한 문제에 적용할 수 있으며, 특히 최소 비용 경로나 최적해를 찾는 문제에 유용합니다.
