8039 : 미로 탐색
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N \times M$ 크기의 미로가 주어집니다. 각 칸은 벽(
출발점
[제약 조건]
• $1 \le N, M \le 1{,}000$
• 시작점
#), 통로(.), 출발점(A), 도착점(B) 중 하나입니다.출발점
A에서 출발하여 도착점 B에 도달하는 최단 경로를 구하고자 합니다. 이동 방향은 상하좌우로만 가능합니다.[제약 조건]
• $1 \le N, M \le 1{,}000$
• 시작점
A와 도착점 B가 격자 내에 주어집니다.입력 설명
첫째 줄에 미로의 세로 크기 $N$과 가로 크기 $M$이 공백으로 구분되어 주어집니다. ($1 \le N, M \le 1000$)
다음 $N$개의 줄에 각각 $M$개의 문자로 미로 정보가 주어집니다.
다음 $N$개의 줄에 각각 $M$개의 문자로 미로 정보가 주어집니다.
출력 설명
도착점
첫째 줄에
둘째 줄에 최단 경로의 길이(이동 횟수)를 출력합니다.
셋째 줄에 이동 경로를 나타내는 문자열(
만약 도착점에 도달할 수 없다면
B에 도달할 수 있는 경로가 존재한다면:첫째 줄에
YES를 출력합니다.둘째 줄에 최단 경로의 길이(이동 횟수)를 출력합니다.
셋째 줄에 이동 경로를 나타내는 문자열(
L, R, U, D로 구성)을 출력합니다.만약 도착점에 도달할 수 없다면
NO를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 8
########
#A#...##
#.#.#.B#
#......#
########
출력 예시
COPY
복사되었습니다!
복사되었습니다!
YES
9
LDDRRRRRU도움
가중치가 1인 격자 그래프에서의 최단 경로는 너비 우선 탐색(BFS)을 통해 보장됩니다.
탐색 시 각 정점을 큐에 넣으며 방문 표시를 하고, 이전 정점 정보(parent)와 이동 방향을 기록합니다. 도착점
탐색 시 각 정점을 큐에 넣으며 방문 표시를 하고, 이전 정점 정보(parent)와 이동 방향을 기록합니다. 도착점
B에 도달하면 역추적하여 최단 경로 문자열을 구성합니다. 큐에 원소를 넣는 시점에 바로 방문 처리를 해야 중복 삽입으로 인한 런타임 타임아웃을 막을 수 있습니다.