[백준 코딩테스트] 백준 1375번 나이

내 풀이

먼저 이 문제를 풀기 위해서는

• 나이를 방향 그래프로 표현
• 이때 나이라고 생각하지 않고 갈 수 있는 방향이 있는지 없는지 확인
• 없다면 "gg" 출력

입력이 다음과 같이 주어졌을 때를 생각해보자.

4 2
1 2
2 3
4
1 2
2 3
1 3
1 4

이름	ID
1	0
2	1
3	2

그럼 다음과 같은 id가 getId() 메서드에 의해 생성된다. 4는 불리지 않았기에 만들어지지 않는다.

1 2 → edges[0].add(1)
2 3 → edges[1].add(2)

다음과 같은 입력에 edges 그래프가 연결된다. 이렇게 되면 4는 고립되게 된다.

쿼리	의미	판단	결과
1 2	1 → 2 가능?	O	1
2 3	2 → 3 가능?	O	2
1 3	1 → 2 → 3 가능?	O	1
1 4	1 ↛ 4, 4 ↛ 1	X	gg

내 코드

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);
    static Map<String, Integer> comp = new HashMap<>();
    static List<List<Integer>> edges = new ArrayList<>();
    static int idCount = 0;

    public static void main(String[] args) throws Exception {
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); 
        int m = Integer.parseInt(st.nextToken());

        // 간선 정보 등록
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            String a = st.nextToken();
            String b = st.nextToken();
            int u = getId(a);
            int v = getId(b);
            edges.get(u).add(v); // 경로 등록
        }

        int q = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        // 쿼리 처리
        for (int i = 0; i < q; i++) {
            st = new StringTokenizer(br.readLine());
            String a = st.nextToken();
            String b = st.nextToken();

            // 경로가 없으면 -1 삽입
            int u = comp.getOrDefault(a, -1);
            int v = comp.getOrDefault(b, -1);

            if (u == -1 || v == -1) {
                sb.append("gg ");
                continue;
            }

            if (reachable(u, v)) sb.append(a).append(" ");
            else if (reachable(v, u)) sb.append(b).append(" ");
            else sb.append("gg ");
        }
        System.out.println(sb);
    }

    // 이름을 ID로 변환하고, 처음 보는 이름이면 리스트도 확장
    static int getId(String name) {
        if (!comp.containsKey(name)) {
            comp.put(name, idCount++);
            edges.add(new ArrayList<>());
        }
        return comp.get(name);
    }

    // BFS로 a → b 도달 가능한지 확인
    static boolean reachable(int a, int b) {
        boolean[] visited = new boolean[idCount];
        Queue<Integer> q = new ArrayDeque<>();
        q.add(a);
        visited[a] = true;

        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int next : edges.get(cur)) {
                if (next == b) return true;
                if (!visited[next]) {
                    visited[next] = true;
                    q.add(next);
                }
            }
        }
        return false;
    }
}