[구름톤 챌린지] 작은 노드

풀이 과정

1. 먼저 노드들의 연결 정보를 담기 위해서 ArrayList<Integer>[] graph를 선언하였다.
2. 그리고 노드 개수만큼 반복하여 해당 인덱스마다 해당 노드가 연결된 정보를 담을 수 있게 new ArrayList<>();를 통해 할당하였다. 그리고 visited를 통해서는 해당 노드를 방문했을 경우 다음 노드를 방문할 수 있는 용도로 정의하였다.
3. 그 후에 간선의 개수만큼 순회하며 입력된 간선의 정보를 통해 양 노드가 서로 연결되어 있기 때문에 양 노드 모두 해당 인덱스에 대한 ArrayList에 추가하도록 작성했다.
4. 문제 조건 중에 방문할 수 있으면서 번호가 가장 작은 노드로 이동하기 때문에 해당 노드에 연결된 노드들을 오름차순으로 정렬했다.
5. DFS 방식을 사용하여 시작 노드로부터 연결된 노드들을 순회하면 위에서 정렬했기 때문에 가장 먼저 가장 작은 노드가 나오게 된다.
6. 이 때, visited를 통해서 만약 방문한 노드인 경우에는 다음 작은 노드로 넘어가고, 방문하지 않은 경우에는 다시 dfs() 메서드를 호출하여 다음 노드로 넘어간다.
7. 이 때, 방문한 노드들은 visited에 true를 통해 방문하도록 만들고, 다음 노드로 넘어갈 때마다 count를 증가, 마지막 방문한 노드는 lastNode에 정보를 남긴다.
8. 마지막으로 방문한 노드의 개수와 마지막 노드의 번호를 출력한다.

 

코드

import java.io.*;
import java.util.*;

class Main {
	
	static int count = 0;
	static int lastNode = 0;
	static boolean[] visited;
	static ArrayList<Integer>[] graph;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); // 노드의 개수
		int M = Integer.parseInt(st.nextToken()); // 간선의 개수
		int K = Integer.parseInt(st.nextToken()); // 시작 노드의 번호
		graph = new ArrayList[N];
		visited = new boolean[N];
		
		for (int i = 0; i < N; i++) {
			graph[i] = new ArrayList<>();
		}
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
	
			graph[start - 1].add(end - 1);
			graph[end - 1].add(start - 1);
		}
		
		for (int i = 0; i < N; i++) {
			Collections.sort(graph[i]);
		}
		
		count++;
		lastNode = K - 1;
		dfs(lastNode);
		
		System.out.println(count + " " + (lastNode + 1));
	}
	
	public static void dfs(int start) {
		visited[start] = true;
		
		for (int node : graph[start]) {
			if (!visited[node]) {
				count++;
				lastNode = node;
				dfs(node);
				return;
			}
		}
	}
}

 

느낀점

인접행렬, BFS, DFS 중 하나를 선택해서 사용할 수 있지만 좀 더 DFS에 대해서 공부해보고자 DFS를 선택해서 풀면서 좀 더 감을 익힐 수 있었다.