8043 : 0-1 최단 경로
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$R \times C$ 크기의 미로 격자가 주어집니다. 격자의 각 칸에는 알파벳 소문자 중 하나가 적혀 있습니다.
우리는 좌측 상단 $(1,1)$ 칸에서 출발하여 우측 하단 $(R,C)$ 칸까지 도달하려고 합니다.
인접한 상하좌우 칸으로 이동할 때, 이동하는 칸의 알파벳이 현재 칸의 알파벳과 같으면 비용이 0이고, 다르면 비용이 1이 소요됩니다.
$(1,1)$에서 $(R,C)$까지 도달하는 데 필요한 최소 누적 비용을 구하는 프로그램을 작성하시오.
[제약 조건]
• 테스트 케이스 수 $T$
• $1 \le R, C \le 1{,}000$
우리는 좌측 상단 $(1,1)$ 칸에서 출발하여 우측 하단 $(R,C)$ 칸까지 도달하려고 합니다.
인접한 상하좌우 칸으로 이동할 때, 이동하는 칸의 알파벳이 현재 칸의 알파벳과 같으면 비용이 0이고, 다르면 비용이 1이 소요됩니다.
$(1,1)$에서 $(R,C)$까지 도달하는 데 필요한 최소 누적 비용을 구하는 프로그램을 작성하시오.
[제약 조건]
• 테스트 케이스 수 $T$
• $1 \le R, C \le 1{,}000$
입력 설명
첫째 줄에 테스트 케이스의 개수 $T$가 주어집니다.
각 테스트 케이스마다 첫째 줄에 격자의 세로 크기 $R$과 가로 크기 $C$가 공백으로 구분되어 주어집니다. ($1 \le R, C \le 1000$)
다음 $R$개의 줄에 각각 $C$개의 문자로 격자 알파벳 정보가 주어집니다.
각 테스트 케이스마다 첫째 줄에 격자의 세로 크기 $R$과 가로 크기 $C$가 공백으로 구분되어 주어집니다. ($1 \le R, C \le 1000$)
다음 $R$개의 줄에 각각 $C$개의 문자로 격자 알파벳 정보가 주어집니다.
출력 설명
각 테스트 케이스마다 $(1,1) $(R,C) 가는 최소 비용을 한 줄에 하나씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
1
2 2
AA
AB
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1도움
이 문제는 가중치가 0 또는 1만 존재하는 그래프에서의 최단 경로 문제입니다. 일반 다익스트라($O(E \log V)$)보다 빠른 **0-1 BFS($O(V+E)$)** 기법을 적용할 수 있습니다.
양방향 큐(Deque)를 구성하여 탐색하며, 다음 칸으로 이동하는 비용이 0이면 큐의 앞에(
양방향 큐(Deque)를 구성하여 탐색하며, 다음 칸으로 이동하는 비용이 0이면 큐의 앞에(
appendleft), 비용이 1이면 큐의 뒤에(append) 노드를 삽입합니다. 이렇게 하면 큐가 항상 정렬된 상태를 유지하므로 우선순위 큐 없이 $O(R \times C)$에 정답을 구할 수 있습니다.