[문제 풀이] 백준 5567번 결혼식 JAVA

문제

 

  문제접근 방법   

해당 문제는 상근이가 자신의 결혼식에 자신의 친구와 친구의 친구까지 부르려고 할 때 몇 명을 초대할 수 있는지 구하는 프로그램을 작성하는 문제이다. 

처음 문제를 읽고 bfs나 dfs를 통해 문제를 해결해야겠다는 생각이 들었고 그중 bfs를 선택해 문제를 풀이하기로 결정하였다.

먼저 인접리스트를 통해 각 관계를 저장하는데 이때 dfs에서처럼 depth를 통해서 친구의 친구까지를 선택하는 방식으로 작성하였다. 

 

< 초기 코드  >

import java.util.*;

public class Main{
    public static List<ArrayList<Integer>> list=new LinkedList<>();
    public static Set<Integer> set=new HashSet<>();
    public static boolean visited[];
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int m=s.nextInt();
        visited=new boolean[n+1];
        for(int i=0;i<=n;i++){
            list.add(new ArrayList<>());
        }
        for(int i=0;i<m;i++){
            int n1=s.nextInt();
            int n2=s.nextInt();
            list.get(n1).add(n2);
            list.get(n2).add(n1);
        }
        bfs(1);
        //System.out.println(set);
        System.out.print(set.size()-1);
    }
    public static void bfs(int i){
        Queue<int[]> q=new LinkedList<>();
        int depth=0;
        q.offer(new int[]{i,depth});
        set.add(1);
        visited[i]=true;
        while(!q.isEmpty()){
            int num[]=q.poll();
            if(num[1]==3)break;
            for(int k=0;k<list.get(num[0]).size();k++){
               
                    q.offer(new int[]{list.get(num[0]).get(k),num[1]+=1});
                    set.add(list.get(num[0]).get(k));
                    visited[list.get(num[0]).get(k)]=true;
                
            }
        }
    }
}

초기에는 방문처리를 해주어야한다고 생각해 방문처리를 해주려고 노력했지만 문제를 풀고 생각하면 생각할수록 필요 없는 부분 같아 아래와 같이 수정하였다.

< 최종 코드 >

import java.util.*;

public class Main{
    public static List<ArrayList<Integer>> list=new LinkedList<>();
    public static Set<Integer> set=new HashSet<>();
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int m=s.nextInt();
        for(int i=0;i<=n;i++){
            list.add(new ArrayList<>());
        }
        for(int i=0;i<m;i++){
            int n1=s.nextInt();
            int n2=s.nextInt();
            list.get(n1).add(n2);
            list.get(n2).add(n1);
        }
        bfs(1);
        System.out.print(set.size()-1);
    }
    public static void bfs(int i){
        Queue<int[]> q=new LinkedList<>();
        int depth=0;
        q.offer(new int[]{i,depth});
        set.add(1);
        while(!q.isEmpty()){
            int num[]=q.poll();
            if(num[1]==2)break;
            for(int k=0;k<list.get(num[0]).size();k++){
               
                    q.offer(new int[]{list.get(num[0]).get(k),num[1]+1});
                    set.add(list.get(num[0]).get(k));
                
            }
        }
    }
}

인접리스트를 통해서 각 친구 관계를 입력받고 1번 기준 친구의 친구 즉 depth==2까지만 카운트하는 것이다.

여기서 방문처리가 없기 때문에 어떤 식으로 카운트를 해줘야하나 고민하던 중 방문처리를 해주고 나중에 카운트하는 방식도 있겠지만 여기서는 방문처리 없고 Set을 통해 중복 없이 카운트하는 방식으로 코드를 작성하였다.

코드를 작성하고 보니 이문제는 굳이 bfs로 풀이하는  것보다는 dfs로 문제를 해결하는 것이 더 좋아보였다.

 

  마무리  

 

  추가 코드 분석 및 풀이  

위에서 언급하였듯이 dfs로 풀이하는 것이 더 좋아 보였기에 풀이해보려고 한다.

 

< 추가 코드 ver DFS >

- 추후 업데이트 예정

 

 참고 자료