링크

결혼식

문제

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.

상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다. (1 ≤ ai < bi ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다.

출력

첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.

풀이

먼저 리스트를 생성하여 각 연결을 리스트에 담는다.
다음으로 dfs를 통해 1부터 시작하여 리스트에 담긴값과 연결되어있는 리스트를 depth를 1씩 증가시켜주며 depth가 2가될때 까지 찾는다.(친구의친구==2)

코드

package com.company.GraphSearch;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Wedding {
    static int N,M;
    static boolean[]visit,check;
    static ArrayList<Integer>list[];
    static void input() throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());
        M=Integer.parseInt(br.readLine());
        list=new ArrayList[N+1];
        visit=new boolean[N+1];
        check=new boolean[N+1];
        for(int i=1;i<=N;i++){
            list[i]=new ArrayList<>();
        }
        for(int i=0;i<M;i++){
            StringTokenizer st=new StringTokenizer(br.readLine()," ");
            int x=Integer.parseInt(st.nextToken());
            int y=Integer.parseInt(st.nextToken());
            list[x].add(y);
            list[y].add(x);
        }

        dfs(0,1);
    }
    static void dfs(int depth,int current){
        if(depth==2){
            return;
        }
        for(int next:list[current]){
                visit[next]=true;
                dfs(depth + 1, next);


        }
    }
    public static void main(String[] args) throws IOException {
        input();
        int cnt=0;
        for(int i=2;i<=N;i++){
            if(visit[i]) {
                cnt++;
            }
        }

        System.out.println(cnt);
    }
}

아쉬웠던점

전에 풀었던 효율적인 해킹문제를 풀며 그땐 bfs로 풀었기에 양방향을 설정해주지 않았었다.
그치만 이번엔 dfs로풀며 양방향 설정을 해줬어야하는데 그것때문에 시간이 좀더 오래걸렸었다.
문제를 좀더 똑바로 읽자!!