오답노트 #24479 : 알고리즘 수업 - 깊이 우선 탐색 1

풀이방법 및 문제점

2022.05.27

지금까지 몇 개의 노드를 방문해왔는지 저장하는 변수 num을 전역변수로 설정하지 않고 재귀 시마다 넘겨주는 변수로 선언하였더니 틀린 답이 도출되었다. 이 점을 기억하기 위해 오답노트에 적는다.

틀렸던 이유는, 새로 방문하는 노드를 만날 때 dfs 함수 내에서 1 증가시켜주었던 num의 값이, 재귀가 끝나 이전 노드로 거슬러올라갈 때 다시 1씩 줄어든다는 데 있었다.

이것을 알아채는 것에는 백준의 질문 게시판에 있던 다음의 테스트케이스가 도움이 되었다.

 

6 7 1
1 6
1 2
2 6
2 3
2 4
3 5
4 5

1 -> 2 -> 3 -> 4 -> 5 -> 6
위 소스는 아래와 같이 나오네요.
1
2
3
5
4
3

내 코드에서도 똑같은 오답이 나와서 왜 그럴까를 고민해봤더니 문제점을 찾아낼 수 있었다.

이 질문글의 링크는 다음과 같다. https://www.acmicpc.net/board/view/83904

 

이 점을 고쳤더니 바로 정답처리가 되었다.

정답 게시글 바로가기

 

코드

Java(2022.05.27)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
	static ArrayList<TreeSet<Integer>> arr;	//간선 정보 저장용 트리셋 배열
	static boolean[] visited;	//방문여부 기록용 배열
	static int[] answer;	//정답(노드별 방문순서) 저장용 배열

	public static void dfs(int cur, int num) {	//cur은 이번 노드의 번호, num은 방문 순서
		//이미 방문한 노드라면 return
		if(visited[cur]) return;
		//방문했음을 표시하고 해당 노드의 방문 순서를 기록
		visited[cur] = true;
		answer[cur] = num++;
		//연결된 다른 노드들로 넘어가기(재귀)
		for(int i: arr.get(cur)) dfs(i, num);
	}
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		//N,M,r 읽어오기
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken());
		
		arr = new ArrayList<TreeSet<Integer>>();
		for(int i = 0; i<n+1; i++) arr.add(new TreeSet<Integer>());
		
		//간선 정보를 읽어와 저장
		for(int i = 0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr.get(a).add(b);
			arr.get(b).add(a);
		}
		
		//깊이우선탐색을 하며 정답 도출
		visited = new boolean[n+1];	//자동으로 false로 초기화됨
		answer = new int[n+1];	//자동으로 0으로 초기화됨
		dfs(r,1);
		
		//정답 출력
		StringBuilder sb = new StringBuilder();
		for(int i= 1; i<n+1; i++) sb.append(answer[i] + System.lineSeparator());
		System.out.print(sb);
	}

}