5567 - 결혼식 (Java)

 

---

 

문제

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

 

풀이

문제는 단순하다.

 

나는 맵을 활용해서 풀었다.

 

key 값으로 대상 동창을 넣고, value 로는 Set으로 친구 목록을 추가했다.

친구는 양방향 관계니까 반대로도 넣어준다.

 

그런 다음 상근이(1번)의 친구들을 세어주고,

그 친구들의 친구들을 세어주면 끝이다.

 

값을 넣어줄때 동창별로 친구 목록을 Set에 저장해뒀으니 이를 활용하면 된다.

 

정답도 Set을 이용해서 중복을 없애면 된다.

단, 이럴 경우 상근이가 친구가 0명일때를 제외하고 답에 상근이 카운트도 들어가니,

그 부분만 예외처리 해주면 된다.

 

코드

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

public class Main {

    public void solution() throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        Set<Integer> answer = new HashSet<>();
        Map<Integer, HashSet<Integer>> map = new HashMap<>();

        for(int i=0; i<n; i++){
            map.put(i+1, new HashSet<>());
        }

        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int first = Integer.parseInt(st.nextToken());
            int second = Integer.parseInt(st.nextToken());

            HashSet<Integer> firstSet = map.get(first);
            firstSet.add(second);
            map.put(first, firstSet);

            HashSet<Integer> secondSet = map.get(second);
            secondSet.add(first);
            map.put(second, secondSet);
        }

        ArrayList<Integer> friends = new ArrayList<>();
        HashSet<Integer> firstFriend = map.get(1);

        for (Integer i : firstFriend) {
            friends.add(i);
            answer.add(i);
        }

        for (Integer friend : friends) {
            answer.addAll(map.get(friend));
        }

        if(answer.contains(1)){
            System.out.println(answer.size()-1);
            return;
        }

        System.out.println(answer.size());

    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

}

 

후기