7289 : 재귀 미로 탐색
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N \times M$ 크기의 미로에서 시작점 $(0, 0)$에서 출구 $(N-1, M-1)$까지 DFS(깊이 우선 탐색)로 경로를 찾으십시오.
0은 이동 가능, 1은 벽입니다. 상하좌우 4방향으로 이동 가능합니다.
경로가 존재하면 첫 번째 발견된 경로의 좌표 순서를 출력합니다.
※ 여러 경로가 존재할 경우, 방향 탐색 우선순위는 우측 → 하단 → 좌측 → 상단 순서입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
0은 이동 가능, 1은 벽입니다. 상하좌우 4방향으로 이동 가능합니다.
경로가 존재하면 첫 번째 발견된 경로의 좌표 순서를 출력합니다.
※ 여러 경로가 존재할 경우, 방향 탐색 우선순위는 우측 → 하단 → 좌측 → 상단 순서입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 미로 크기 $N$, $M$이 주어집니다. ($2 \le N, M \le 20$)
둘째 줄부터 $N$개의 줄에 미로 정보가 주어집니다. (0: 길, 1: 벽)
둘째 줄부터 $N$개의 줄에 미로 정보가 주어집니다. (0: 길, 1: 벽)
출력 설명
경로가 존재하면 좌표 리스트를
경로가 없으면
(x,y) -> (x,y) -> ... 형식으로 출력합니다.경로가 없으면
NO PATH를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3
0 0 0
1 1 0
0 0 0
출력 예시
COPY
복사되었습니다!
복사되었습니다!
(0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2)도움
DFS로 구현하십시오. 방문 표시를 하여 무한 루프를 방지하고, 탈출구 도달 시 경로를 출력합니다. 막다른 길은 백트래킹합니다.