Algorithm, Problem Solving/백준(boj)

[백준][Java] 5107 - 마니또

태오님 2023. 10. 15.

목차

     

    문제 정보

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

     

    5107번: 마니또

    N명의 사람들이 있다. 이들은 각자 다른 한 명의 이름이 적힌 쪽지를 받아서, 그 사람에게 몰래 선행을 베푼다. 이때 자기 자신의 이름을 받을 수는 없으며, 선행을 받은 사람은 누가 자신을 도와

    www.acmicpc.net

    난이도 : S1

    유형 : Cycle Disjoint-Set, DFS, Hash


    문제 풀이

    해쉬맵을 이용하여 입력으로 주어지는 사람 이름에 고유한 번호를 부여해 준다.

    사람이름 두 개가 입력될 때마다 고유한 번호 두 개를 얻어낸 다음 연결하여 그래프를 구성하면 된다.

     

    방문하지 않은 곳을 차례대로 DFS 탐색을 진행한다.

    만약 탐색 로직 실행 중 이미 탐색했던 곳을 만난다면 순열을 이루는 것이니 결과에 더해주면 된다.


    코드

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.StringTokenizer;
    
    /**
     * BOJ_5107
     * author_devteo77
     */
    
    public class Main {
    
        int T;
        int N;
        int res;
        HashMap<String, Integer> map;
        ArrayList<Integer>[] edges;
        boolean[] isVisited;
    
        public void execDFS(int cur) {
            for (int next : edges[cur]) {
                if (isVisited[next]) {
                    res++;
                    return;
                }
    
                isVisited[next] = true;
                execDFS(next);
            }
        }
    
        public void solution() throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringBuilder sb = new StringBuilder();
            StringTokenizer st;
    
            T = 1;
            while (true) {
                N = Integer.parseInt(br.readLine());
                if (N == 0) {
                    break;
                }
    
                int number = 1;
                map = new HashMap<>();
                edges = new ArrayList[N + 1];
                for (int i = 1; i <= N; i++) {
                    edges[i] = new ArrayList<>();
                }
    
                for (int i = 0; i < N; i++) {
                    st = new StringTokenizer(br.readLine());
                    String from = st.nextToken();
                    String to = st.nextToken();
    
                    if (!map.containsKey(from)) {
                        map.put(from, number++);
                    }
    
                    if (!map.containsKey(to)) {
                        map.put(to, number++);
                    }
    
                    edges[map.get(to)].add(map.get(from));
                }
    
                res = 0;
                isVisited = new boolean[N + 1];
                for (int i = 1; i <= N; i++) {
                    if (!isVisited[i]) {
                        isVisited[i] = true;
                        execDFS(i);
                    }
                }
    
                sb.append(T++).append(" ").append(res).append('\n');
            }
    
            System.out.print(sb);
        }
    
        public static void main(String[] args) throws IOException {
            new Main().solution();
        }
    }

    댓글