[코딩테스트 챌린지] 백준 5567 결혼식 (java)

문제

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

 

문제 탐색하기

1. 문제 유형 파악하기

친구 관계가 주어지는 것을 보았을 때 a와 b는 친구라는 뜻은 b와 a도 친구라는 뜻입니다. 이를 통해서 인접행렬을 통해서 친구관계를 나타낼 수 있었습니다. 

또 문제 조건 중에서 결혼식에 초대하는 사람은 상근이의 친구와 친구의 친구까지만 초대하는 조건이 있었습니다. 이를 통해서 dfs 를 구현하되 depth를 2로 제한을 두어 결혼식에 초대하는 동기의 수를 구할 수 있을 것 입니다.

 

2. 인접 행렬 구현하기

입력받는 친구관계를 통해 친구관계 배열인 connect에 친구일 경우 1을 삽입해줍니다.

connect[a][b] = connect[b][a] = 1

 

3. DFS 구현하기

dfs를 재귀적으로 호출할때 거치는 친구를 True로 저장하는 배열을 선언합니다.

dfs는 상근이의 번호인 1을 시작으로 인접한 노드를 모두 탐색하고 해당 노드의 인접한 노드까지 최대 2번까지만 탐색을 진행합니다.

그럼 depth가 2인 동기의 수를 구할 수 있습니다.

 

코드 설계하기

1. 친구관계 배열을 connect로 선언하여 서로 친구일 경우 1을 삽입합니다.
2. dfs를 구현하는데 상근이 부터 시작하므로 인자는 1하고 depth를 측정할 변수를 넣어서 시작합니다.
3. n까지를 탐색하면서 connect 배열에서 친구관계로 선언된 친구일 경우 방문했다는 flag를 세우고 다시 dfs를 재귀호출 합니다.
4. 재귀호출을 하면서 깊이가 2가 되면 해당 loop는 종료합니다.
5. 최종적으로 어떤 친구를 방문했는지가 결혼식에 초대할 동기이므로 총 TRUE의 개수를 출력합니다.

 

정답 코드

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

public class Wedding {

    static int n,m;
    static int[][] connect;
    static boolean[] visit;

    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(reader.readLine());
        m = Integer.parseInt(reader.readLine());

        connect = new int[n+1][n+1];
        visit = new boolean[n+1];

        StringTokenizer st;
        for(int i=0; i<m; i++){
            st = new StringTokenizer(reader.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            connect[a][b] = connect[b][a] = 1;
        }

        dfs(1, 0);

        int count = 0;
        for(int i=2; i<visit.length; i++){
            if(visit[i]) count++;
        }
        System.out.println(count);
    }

    public static void dfs(int num, int depth){
        if(depth == 2) return;

        for(int i=1; i<=n; i++){
            if(connect[num][i] == 1){
                visit[i] = true;
                dfs(i, depth+1);
            }
        }

    }
}