[구름톤 챌린지] 연합

풀이 과정

처음에는 입력값도 크고 그래서 잠시 유니온파인드인가? 라는 착각을 했었다.. 근데 그러한 문제는 아닌거 같고 그냥 DFS로 풀어보기로 했다. 여기서 핵심은 임의의 두 섬 a와 b에 대해, a번 섬에서 b번 섬으로 직접 이동할 수 있는 다리와 b번 섬에서 a번 섬으로 직접 이동하 룻 있으면, 두 섬은 연합을 결성하는 것이다. 그리고 주의해야할 점으로 a와 b가 연합을 결성하고 b와 c가 여합을 결성했다면 a와 c 역시 위 조건을 만족하지 않더라도 같은 연합에 속해있다고 보는 것이다. 따라서 예제 2번에서 1이 출력되는 것이다.

 

static int count = 0;
static boolean visited[];
static ArrayList<Integer>[] graph;

먼저, static 필드로는 count, visited[], grah를 선언했다. 지금보니 count는 static일 필요는 없는것 같다. 방문한 적이 있는 정보를 담은 visited와 연결 정보를 담은 graph를 위와 같이 선언했다.

 

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);
}

위 코드처럼 초기화를 진행했다. 그러면 이제 풀 준비 완료!

 

for (int i = 0; i < N; i++) {
    if (!visited[i]) {
        count++;
        dfs(i);
    }
}

N개의 노드를 돌면서 0부터 시작되는 연합마을들을 모두 찾고 루프를 돌다 마을 5에서 visited[5]가 방문한 적이 없다면 새로운 연합이 생긴 것이기 때문에 count++;을 해주고 마을 5와의 연합마을을 찾으려 dfs(5)를 실행시키면 된다!

 

public static void dfs(int node) {
    visited[node] = true;

    for (int otherNode : graph[node]) {
        if (!visited[otherNode] && graph[otherNode].contains(node)) {
            dfs(otherNode);
        }
    }
}

dfs() 메서드가 실행되면 방문했기 때문에 visited[node] = true;를 실행해주고, 옆 마을 노드들을 순회하면서 방문한 적이 없으면서 옆 마을 노드에서도 현재 자신의 마을을 건너는 다리가 있으면 연합이기 때문에 dfs(otherNode)를 실행해준다! 이렇게 DFS를 실행하여 현재 자신의 마을의 연합들을 모두 찾아갈 수 있다!

 

코드

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

class Main {
	
	static int count = 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());
		visited = new boolean[N];
		graph = new ArrayList[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);
		}
		
		for (int i = 0; i < N; i++) {
			if (!visited[i]) {
				count++;
				dfs(i);
			}
		}
		
		System.out.println(count);
	}
	
	public static void dfs(int node) {
		visited[node] = true;
		
		for (int otherNode : graph[node]) {
			if (!visited[otherNode] && graph[otherNode].contains(node)) {
				dfs(otherNode);
			}
		}
	}
}

 

느낀점

dfs 문제에 대해 좀 더 가까워진 기분이 들었다.