백준 - 결혼식(Java BFS)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처 : https://www.acmicpc.net/problem/5567

[문제 설명]

친구랑 친구의 친구만 초대해라.

[접근 방법]

순수 트리 문제인줄 알고 골랐는데 그래프 문제였다. 트리도 그래프가 맞긴 한데;

처음엔 맵을 이용해서 풀려고 했는데, (2,1) 이런 형식으로 입력이 올 수도 있어서 그래프를 이용해 풀었다.

그래프를 2차원 배열로 구현할까도 싶었지만, 일일이 모든 노드가 연결 됐는지 파악하기 보다는(O(V^2)) 연결된 노드만 추가하는(O(V+E)) 연결리스트가 나아보여서 연결 리스트로 구현했다.

검색은 BFS

시간복잡도는 O(V+E) 

정점의 개수 = 친구 명수

간선의 개수 = 리스트의 길이

 

[자바 코드]

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


public class Main {
    public static void main(String[] args) throws IOException {
        int cntOfInvitedFriends = 0;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        // 배열 0부터 잡기로 함.
        List<Integer>[] graph = new LinkedList[n];
        boolean[] isVistedNode = new boolean[n];

        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            // 0부터 시작이라 좌표에 -1해줌. graph[0][0] == (1,1)
            int y = Integer.parseInt(st.nextToken()) - 1;
            int x = Integer.parseInt(st.nextToken()) - 1;

            if (graph[y] == null) {
                graph[y] = new LinkedList<>();
            }
            if (graph[x] == null) {
                graph[x] = new LinkedList<>();
            }

            graph[y].add(x);
            graph[x].add(y);
        }

        // 친구가 한명도 없을 때
        if (graph[0] == null) {
            System.out.println(cntOfInvitedFriends);
            return;
        }

        int depth = 0;
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        while (!q.isEmpty()) {
            int cntOfSiblings = q.size();

            // 같은 depth에 있는 애들 모두 체크
            for (int i = 0; i < cntOfSiblings; i++) {
                int currentFriend = q.poll();
                if (isVistedNode[currentFriend]) {
                    continue;
                }
                isVistedNode[currentFriend] = true;
                cntOfInvitedFriends++;

                for (int j = 0; j < graph[currentFriend].size(); j++) {
                    int childNode = graph[currentFriend].get(j);
                    q.offer(childNode);
                }
            }

            if (++depth > 2) {
                break;
            }
        }

        // 자기 자신도 포함했으므로 1을 빼준다.
        System.out.println(cntOfInvitedFriends-1);
    }
}