6110 : 미로 최단 경로 출력
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N×M 크기의 미로에서 시작점 (r1, c1)에서 도착점 (r2, c2)까지 갈 수 있는 최단 경로의 구체적인 경로 리스트를 출력하는 프로그램을 작성하십시오.
최단 경로가 여러 개일 경우, 상하좌우(U, D, L, R) 순서대로 탐색을 시도하는 표준 BFS 알고리즘에 기반해 경로를 찾으십시오.
최단 경로가 여러 개일 경우, 상하좌우(U, D, L, R) 순서대로 탐색을 시도하는 표준 BFS 알고리즘에 기반해 경로를 찾으십시오.
입력 설명
첫째 줄에 행 크기 N과 열 크기 M (1 ≤ N, M ≤ 100)이 주어집니다.
둘째 줄부터 N개의 줄에 격자의 정보가 공백 구분되어 주어집니다. (0은 이동 가능, 1은 벽)
마지막 줄에는 시작 좌표 r1, c1과 도착 좌표 r2, c2가 공백으로 구분되어 주어집니다. (0-indexed)
둘째 줄부터 N개의 줄에 격자의 정보가 공백 구분되어 주어집니다. (0은 이동 가능, 1은 벽)
마지막 줄에는 시작 좌표 r1, c1과 도착 좌표 r2, c2가 공백으로 구분되어 주어집니다. (0-indexed)
출력 설명
최단 경로 상에 있는 정점의 좌표 목록을 시작점부터 도착점까지 공백으로 구분하여
r,c 형태로 순서대로 출력합니다. (경로가 없으면 -1을 출력합니다.)
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3
0 1 0
0 0 0
0 1 0
0 0 2 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
0,0 1,0 1,1 1,2 2,2도움
BFS 탐색을 수행할 때
parent[next] = current 와 같이 각 노드의 직전 방문 위치를 기록해두고, 도착점에 도달했을 때 parent 포인터를 역추적하여 시작점까지의 경로를 완성한 뒤 역순으로 출력하십시오.