백준 24480 - 알고리즘 수업 - 깊이 우선 탐색 2 (java)

https://www.acmicpc.net/problem/24480

DFS를 이용해 정점들을 탐색하는 순서를 출력하는 것이다.

문제를 잘 읽어야 하는데 첫째 줄 = 1번 노드라는 뜻이고 1번 노드를 1번째에 방문했다는 뜻이다.

즉, 만약 start인 R이 2였다면 예제 출력에서 두번째 줄이 무조건 1일 것이다.

그것이 2부터 시작했다는 뜻이기 때문이다.

따라서 몇 번째로 방문한 노드인지 알기 위해 cnt 변수를 추가해주고

isVisited 배열을 통해 0인지 아닌지로 방문했는지를 판단하고 cnt를 이용해 몇번째로 방문했는지를 넣어주면 된다.

연결을 표시하는 graph는 각각 몇개가 연결되어 있는지 모르기 때문에 ArrayList로 2차원 배열을 만들어 만든다.

graph.get(node1) = {4,2} 라면 1번 노드는 4번과 2번노드랑 연결되어 있다는 것이다.

내림차순으로 방문하라했기 때문에 내림차순으로 정렬을 해주면 된다.

public class Main {  
  
static int cnt;  
static int[] isVisited;  
static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();  
  
public static void main(String[] args) throws Exception {  
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
	StringTokenizer st;  
	StringBuilder sb = new StringBuilder();  
  
	st = new StringTokenizer(br.readLine());  
  
	int N = Integer.parseInt(st.nextToken()); //정점의 수  
	int M = Integer.parseInt(st.nextToken()); //간선의 수  
	int R = Integer.parseInt(st.nextToken()); //시작 정점  
  
	isVisited = new int[N + 1];  
  
	for(int i = 0; i <= N; i++)  
	{  
		graph.add(new ArrayList<Integer>());  
	}  
  
	for(int i = 0; i < M; i++)  
	{  
		st = new StringTokenizer(br.readLine());  
		int node1 = Integer.parseInt(st.nextToken());  
		int node2 = Integer.parseInt(st.nextToken());  
  
		graph.get(node1).add(node2);  
		graph.get(node2).add(node1);  
	}  
  
	for(int i = 1; i <= N; i++)  
	{  
		Collections.sort(graph.get(i), (a,b) -> b-a);  
	}  
  
	cnt = 1;  
	dfs(R);  
  
	for(int i = 1; i < isVisited.length; i++)  
	{  
		sb.append(isVisited[i]).append("\n");  
	}  
	System.out.print(sb);  
}  
  
public static void dfs(int node)  
{  
	isVisited[node] = cnt; 
  
	for(int i = 0; i < graph.get(node).size(); i++)  
	{  
		int newNode = graph.get(node).get(i);  
		if(isVisited[newNode] == 0)  
		{  
			cnt++;  
			dfs(newNode);  
		}  
	}  
}