[백준] 5567번. 결혼식(JAVA)

문제

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

---

풀이(17분)

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

public class Main {

    static int n, m;
    static boolean[][] arr;
    static boolean[] check;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        arr = new boolean[n][n];
        check = new boolean[n];

        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            arr[a][b] = true;
            arr[b][a] = true;
        }

        int answer = 0;
        check[0] = true;
        dfs(0, 0);
        for(int i = 0; i < n; i++){
            if(check[i]){
                answer++;
            }
        }

        System.out.println(answer - 1);
    }

    static void dfs(int friend, int depth){
        if(depth == 2){
            check[friend] = true;

            return;
        }

        for(int i = 0; i < n; i++){
            if(arr[friend][i]){
                check[i] = true;
                dfs(i, depth+1);
            }
        }
    }
}

 

실제 코딩테스트 상황이라고 생각하고 풀어보았다.

 

한 번밖에 경험해 본 적이 없어서인지 생각보다 조급해졌고, 단순한 문제임에도 조건을 착각해 실수를 했었다.

 

실제로는 간단한 dfs문제로 depth == 2일 때까지만 추적해 주면 되는 문제였다.

 

효율적이게 작성되지는 않았지만 더욱 시간을 줄여가며 연습해야될 것 같다.

 

문제 해결 사고 과정은 다음과 같다.

1. 자기 자신의 친구를 먼저 체크한다. 이 때 자기 자신의 친구는 depth = 1이 된다.

2. 자기 자신의 친구의 친구를 체크한다. 이 때의 depth = 2가 되며, 여기서 return 된다.

3. 최종적으로 체크된 사람들의 값에서 -1을 하여 출력한다.(자기 자신 제외)