문제

문제 바로가기

풀이 코드

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에서 조건문으로 처리해주고 방문 여부도 확인을 해주기 위해 visited 배열 생성을 해주었다!