문제

문제 바로가기

풀이 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[][] computer; // 컴퓨터가 서로 연결된 정보
    static int n; // 컴퓨터 개수
    static int line; // 쌍의 개수
    static StringTokenizer st;
    static boolean[] visited;
    static int count = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        line = Integer.parseInt(br.readLine());
        computer = new int[n + 1][n + 1];
        for (int i = 1; i <= line; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            computer[a][b] = 1;
            computer[b][a] = 1;
        }
        visited = new boolean[n + 1];
        sol(1);
        System.out.println(count);
    }

    public static void sol(int start) {
        visited[start] = true;
        for (int i = 1; i <= n; i++) {
            if (computer[start][i] == 1 && !visited[i]) {
                count++;
                sol(i);
            }
        }
    }
}

간단하게 dfs로 문제를 해결했다. 처음 컴퓨터 연결된 정보를 받을때 양방향 연결을 고려해서 2차원 배열에 각 서로 좌표끼리 1로 값을 넣어두고 dfs안에서는 방문 여부와 연결을 고려해서 재귀를 통해 count 횟수를 출력하면 된다.