[백준] 5567번: 결혼식

 

 

문제 파악

- 친구의 친구까지만 구하기

 

<알고리즘 분류>
-그래프 이론
-그래프 탐색
-너비 우선 탐색

 

접근 방법

-특정 레벨까지만 탐색해야 하므로 완전탐색X BFS접근을 사용해야 한다.

-'친구의 친구'까지라고 명시되어있기 때문에 lev2까지 탐색한다고 힌트를 얻을 수 있음

 

 

코드 구현

package org.server;
import java.io.*;
import java.util.*;

public class Main {
    static boolean[] visited;
    static int N;
    static Map<Integer,List<Integer>> graph;
    static int cnt=0;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());//노드
        int M = Integer.parseInt(br.readLine());//간선
        StringTokenizer st;
        graph = new HashMap<>();
        visited = new boolean[N+1];
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            graph.putIfAbsent(v, new ArrayList<>());
            graph.putIfAbsent(e, new ArrayList<>());
            graph.get(v).add(e);
            graph.get(e).add(v);
        }
        bfs(1);
        System.out.println(cnt);

    }
    public static void bfs(int start){
        Queue<int[]> que = new ArrayDeque<>();
        que.add(new int[]{start,0});
        visited[start]=true;

        while (!que.isEmpty()) {
            int[] arr = que.poll();
            int node = arr[0]; int level = arr[1];

            if(level>2) continue;
            if(level>0) cnt++;
            for(int x:graph.getOrDefault(node,Collections.emptyList())){
                if(!visited[x]){//자식들 방문여부 체크
                    visited[x]=true;
                    que.add(new int[]{x,level+1});
                }
                
            }
        }
        
    }
}

 

배우게 된 점

-완전탐색이 아닌 '친구의 친구'라고 명시해 둔 부분을 유의하자.

-get()부분에서 NPE가 발생했다. 이를 예방하기 위해 getOrDefault()를 사용하도록 하자.

이렇게 하면 null 대신 빈 리스트(Collections.emptyList())를 반환하기 때문에 에러때문에 런타임 에러가 발생할 가능성이 차단된다.