6140 : DFS+BFS 비교
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
동일한 격자 미로 공간에서 시작 좌표가 주어졌을 때, DFS(상하좌우 순서 탐색)와 BFS(상하좌우 순서 탐색)가 각각 방문하게 되는 총 노드 개수와 순서 차이를 확인하는 시뮬레이션 프로그램을 작성하십시오.
0은 빈칸이고 1은 벽입니다. 탐색 순서는 상, 하, 좌, 우 순서로 진행합니다.
0은 빈칸이고 1은 벽입니다. 탐색 순서는 상, 하, 좌, 우 순서로 진행합니다.
입력 설명
첫째 줄에 격자의 크기 N과 M (1 ≤ N, M ≤ 100)이 주어집니다.
둘째 줄부터 N개의 줄에 격자 맵 정보가 공백 구분되어 주어집니다.
마지막 줄에는 시작 좌표 r, c가 공백 구분되어 주어집니다. (0-indexed)
둘째 줄부터 N개의 줄에 격자 맵 정보가 공백 구분되어 주어집니다.
마지막 줄에는 시작 좌표 r, c가 공백 구분되어 주어집니다. (0-indexed)
출력 설명
첫째 줄에 DFS 방문 칸 수 K와 K개의
둘째 줄에 BFS 방문 칸 수 L과 L개의
r,c 좌표 순서를 공백으로 구분하여 출력합니다.둘째 줄에 BFS 방문 칸 수 L과 L개의
r,c 좌표 순서를 공백으로 구분하여 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3
0 0 0
0 1 0
0 0 0
0 0
출력 예시
COPY
복사되었습니다!
복사되었습니다!
8 0,0 1,0 2,0 2,1 2,2 1,2 0,2 0,1
8 0,0 1,0 0,1 2,0 0,2 2,1 1,2 2,2도움
방향 탐색 배열을
dr = [-1, 1, 0, 0], dc = [0, 0, -1, 1] 순서로 지정하고, 각각의 방문 visited 배열을 분리해 DFS와 BFS 방문 로직을 돌리십시오.