[백준] 1375 - 나이(Java)

문제 파악

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

어려운 점

문제의 입출력에 대한 설명이 아쉬웠다.
"이름의 길이는 6byte 이하이다"를 주목하면, 입력으로 주어지는 a, b가 문자열이 될 수 있다는 걸 살포시 유추할 수 있다..
이 부분을 놓쳐 시간을 많이 썼다.

풀이

문제에서는 첫 번째로 대소 관계를 입력받고 두 번째로는 쿼리를 입력받는다.

문제를 해결하기 위해서는 크게 두 가지를 수행해야 한다.

대소 관계 입력 처리 및 관계를 정립

• Map<String, Set<String>>을 선언
  • Key : 나이가 많은 이름 저장
  • Value : Key보다 어린 이름을 저장
• `Alice Jude`, `Alice Tom` 와 같이 이름을 입력받는다면 Map은 다음과 같다.
  • Alice : [Jude, Tom] 의 구조를 갖는다
  • Jude, Tom를 키로 갖는 엔트리는 존재하지 않는다.

쿼리를 입력 처리 및 두 수의 대소비교를 수행

대소를 구분해야 하므로 방향성이 있는 그래프라고 봐도 좋을 듯하다. 이는 DFS로 수행한다.

`Alice Tom`쿼리를 입력받았다고 가정하자

• Alice가 큰 지 검사
  • Alice의 자식 노드를 계속해서 탐색하여 Tom이 있는지를 탐색한다.
  • 자식 노드 중 Tom이 있다면 Alice가 Tom보다 큰 것이므로 Alice를 출력
• Tom이 큰 지 검사
  • Tom의 자식 노드를 탐색하여 Alice가 있는지를 탐색한다.
  • 자식 노드 중 Alice이 있다면 Tom이 Alice보다 큰 것이므로 Tom를 출력
• 위 두 조건을 만족하지 않는다면, 같거나 관계를 정립할 수 없으므로 "gg" 출력

추가적으로 중복방문을 피하기 위해 방문 여부를 체크하는 Set를 사용했다.

이를 코드로 작성하면 다음과 같다.

코드

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

public class Main {
    static final String UNDEFINED = "gg";
    static Map<String, Set<String>> rootMap;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tok = new StringTokenizer(br.readLine(), " ");
        int peopleCount = Integer.parseInt(tok.nextToken());
        rootMap = new HashMap<>();
        int comparisonCount = Integer.parseInt(tok.nextToken());
        for (int i = 0; i < comparisonCount; i++) {
            String[] line = br.readLine().split(" ");
            rootMap.computeIfAbsent(line[0], k -> new HashSet<>()).add(line[1]);
        }
        // query
        int queryCount = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < queryCount; i++) {
            String[] line = br.readLine().split(" ");
            String root = line[0];
            String child = line[1];
            if (isChildOfRoot(root, child, new HashSet<>())) {
                sb.append(root).append(" ");
            } else if (isChildOfRoot(child, root, new HashSet<>())) {
                sb.append(child).append(" ");
            } else {
                sb.append(UNDEFINED).append(" ");
            }
        }
        System.out.println(sb);
    }

    static boolean isChildOfRoot(String root, String target, Set<String> visited) {
        if (!rootMap.containsKey(root)) { // is root
            return false;
        }
        visited.add(root);
        if (rootMap.get(root).contains(target)) {
            return true;
        }
        for (String child : rootMap.get(root)) {
            if (visited.contains(child)) {
                continue;
            }
            if (isChildOfRoot(child, target, visited)) {
                return true;
            }
        }
        return false;
    }
}