(JAVA) [BOJ]백준 11724번, 연결 요소의 개수

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

11724번: 연결 요소의 개수

11724, 연결 요소의 개수

이번 문제는 그래프 이론 과 DFS 를 사용해서 풀어보겠다.

 

# Process

main

: 정점의 개수와 간선의 개수가 주어진다. 정점의 개수만큼 ArrayList 를 만들어주고 양방향 간선을 표시해주면 된다.

 

N = scan.nextInt();
M = scan.nextInt();
adj = new ArrayList[N+1];
visit = new boolean[N+1];

for(int i=1; i<=N; i++) adj[i] = new ArrayList<>();

for(int i=1; i<=M; i++)
{
    int x = scan.nextInt();
    int y = scan.nextInt();
    // 양방향
    adj[x].add(y);
    adj[y].add(x);
}

 

순회

: 1 - N 까지 순회하며 방문하지 않은 정점에 dfs 를 호출해주며, 호출할 때마다 ans 의 카운트를 더해간다.

static void pro() 
{
    int ans = 0;

    for(int i=1; i<=N; i++)
    {
        if(visit[i]) continue;
        dfs(i);
        ans++;
    }
    System.out.println(ans);
}

dfs

: 방문에 대한 처리는 선행하기 때문에 들어온 x 좌표에 대한 방문을 처리해주고 ArrayList (adj) 와 연결되어 있는 모든 정점을 순회하며 방문처리를 진행한다.

static void dfs(int x)
{
    visit[x] = true;

    for(int k : adj[x])
    {
        if(visit[k]) continue;

        dfs(k);
    }
}

 

전체 코드

static int N, M;
static ArrayList<Integer>[] adj;
static boolean[] visit;

static void input() 
{
   N = scan.nextInt();
   M = scan.nextInt();
   adj = new ArrayList[N+1];
   visit = new boolean[N+1];

   for(int i=1; i<=N; i++) adj[i] = new ArrayList<>();

   for(int i=1; i<=M; i++)
   {
        int x = scan.nextInt();
        int y = scan.nextInt();
        // 양방향
        adj[x].add(y);
        adj[y].add(x);
   }
}

static void pro() 
{
    int ans = 0;

    for(int i=1; i<=N; i++)
    {
        if(visit[i]) continue;
        dfs(i);
        ans++;
    }
    System.out.println(ans);
}

static void dfs(int x)
{
    visit[x] = true;

    for(int k : adj[x])
    {
        if(visit[k]) continue;

        dfs(k);
    }
}

public static void main(String[] args) 
{
    input();
    pro();
}