6095 : 미로 DFS — 모든 경로 탐색
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N×M 크기의 격자 미로 정보가 주어집니다. 시작점 'S'에서 출발하여 끝점 'E'까지 벽 '#'을 피해 도달할 수 있는 모든 경로를 DFS 탐색을 통해 찾아 출력하십시오.
이동 규칙:
1. 한 칸에서 상, 하, 좌, 우 4방향으로 이동할 수 있습니다.
2. 한 경로 내에서 같은 칸을 두 번 이상 방문할 수 없습니다. (Backtracking 필요)
3. 경로 출력 형식은
[제약 조건]
• 격자 크기: $1 \le N, M \le 7$ (정수)
• 격자 구성: 'S'(시작), 'E'(끝), '.'(이동 가능), '#'(벽)
• 경로가 없으면 빈 출력을 합니다.
이동 규칙:
1. 한 칸에서 상, 하, 좌, 우 4방향으로 이동할 수 있습니다.
2. 한 경로 내에서 같은 칸을 두 번 이상 방문할 수 없습니다. (Backtracking 필요)
3. 경로 출력 형식은
(r1,c1)->(r2,c2)->... 형태여야 하며, 전체 경로 리스트는 문자열 사전순으로 정렬되어야 합니다.[제약 조건]
• 격자 크기: $1 \le N, M \le 7$ (정수)
• 격자 구성: 'S'(시작), 'E'(끝), '.'(이동 가능), '#'(벽)
• 경로가 없으면 빈 출력을 합니다.
입력 설명
첫째 줄에 행 크기 N과 열 크기 M (1 ≤ N, M ≤ 7)이 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 미로의 지도가 주어집니다. ('S'=시작, 'E'=끝, '.'=이동 가능, '#'=벽)
둘째 줄부터 N개의 줄에 걸쳐 미로의 지도가 주어집니다. ('S'=시작, 'E'=끝, '.'=이동 가능, '#'=벽)
출력 설명
첫째 줄에 가능한 모든 경로의 개수를 출력합니다.
둘째 줄부터 각 경로를 사전순으로 한 줄에 하나씩 출력합니다. (경로가 존재하지 않는 경우 0만 출력합니다.)
둘째 줄부터 각 경로를 사전순으로 한 줄에 하나씩 출력합니다. (경로가 존재하지 않는 경우 0만 출력합니다.)
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3
S..
..#
..E
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4
(0,0)->(0,1)->(1,1)->(1,0)->(2,0)->(2,1)->(2,2)
(0,0)->(0,1)->(1,1)->(2,1)->(2,2)
(0,0)->(1,0)->(1,1)->(2,1)->(2,2)
(0,0)->(1,0)->(2,0)->(2,1)->(2,2)도움
DFS 호출 시 현재 위치를 방문 처리하고 재귀 탐색을 마친 뒤, 다시 방문 처리를 해제(visited = false)해야 모든 경로를 완전 탐색할 수 있습니다.