[자바] 백준 1375 - 나이 (java)

목차

문제 : boj1375

 

 

필요 알고리즘

• 그래프 탐색(bfs, dfs), 값/좌표 압축
  
  • 값/좌표 압축이야 그냥 String을 쓰기 편하게 int로 바꾼 것 뿐이고, 풀이는 그냥 bfs를 썼다. 의외로 별다른 것 없이 bfs나 dfs로 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  우선 입력이 String으로 들어오는데 이 부분부터 처리해보자. 그냥 새로운 문자열이 들어오면 그걸 새로운 int로 바꿔주면 된다. 어차피 해당 값은 n이상이 될 수 없으므로 최대 N개의 String이 최대 N인 int로 변환될 뿐이다. 아무래도 정점 번호는 int인게 이후 처리하기 편하다.

if (!comp.containsKey(a)) comp.put(a, num++);
if (!comp.containsKey(b)) comp.put(b, num++);

 

 

  그럼 이 문제는 그냥 N개의 정점에 대해 어떤 쪽이 나이가 많은지에 대한 정보가 주어지고, Q개의 질문으로 어느쪽이 나이가 많은지 알려주면 되는 문제이다.

 

  여기서 어느 쪽이 나이가 많은지에 대한 정보를 간선이라고 생각해보자. 즉 'a b'형태의 입력에 대해 a에서 b로 향하는 단방향 간선을 그어준다고 생각해보자. 이후 Q개의 질문에 대해 a와 b가 주어졌다. a에서 그래프 탐색을 시작하는 중간에 b를 만났다면 그게 뭘 의미할까? a가 b보다 더 나이가 많은질 뜻한다. 반대로 b에서 탐색해서 a가 도달 가능하다면 b가 나이가 많은거다. a->b 혹은 b->a 둘 다 불가하다면 gg 치면 된다.

if (reachable(numA, numB)) sb.append(a).append(' ');
else if (reachable(numB, numA)) sb.append(b).append(' ');
else sb.append("gg ");

 

 

  여기서 문제가 될거라 생각한 부분은 문제에 "모슨되는 데이터는 없습니다." 라는 내용이 없었다는 점이다. 즉, 입력이 '1 2', '2 1' 처럼 모순되는 내용이 있다면 이하 코드만으론 풀 수 없어서 사이클 판정까지 해야해서 좀 까다로워 진다. 그건 일단 제출해보고 틀리면 생각하려고 했는데 그냥 통과했다. 결론적으로 왜 골2인진 잘 모르겠다. 아마 나이에 대한 정보를 간선으로 변경한다는 아이디어 때문일꺼라 생각된다.

 

 

코드 : github

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);

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

    int n;
    List<Integer>[] edges;

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int num = 0;
        Map<String, Integer> comp = new HashMap<>();
        edges = new List[n];
        for (int i = 0; i < n; i++) edges[i] = new ArrayList<>();
        while (m-->0) {
            st = new StringTokenizer(br.readLine());
            String a = st.nextToken();
            String b = st.nextToken();
            if (!comp.containsKey(a)) comp.put(a, num++);
            if (!comp.containsKey(b)) comp.put(b, num++);
            edges[comp.get(a)].add(comp.get(b));
        }

        int q = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (q-->0) {
            st = new StringTokenizer(br.readLine());
            String a = st.nextToken();
            String b = st.nextToken();
            int numA = comp.getOrDefault(a, -1);
            int numB = comp.getOrDefault(b, -1);
            if (numA == -1 || numB == -1) {
                sb.append("gg ");
                continue;
            }

            if (reachable(numA, numB)) sb.append(a).append(' ');
            else if (reachable(numB, numA)) sb.append(b).append(' ');
            else sb.append("gg ");
        }
        System.out.println(sb);
    }

    private boolean reachable(final int a, final int b) {
        boolean[] v = new boolean[n];
        v[a] = true;
        Queue<Integer> q = new ArrayDeque<>();
        q.add(a);

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

                if (v[next]) continue;
                v[next] = true;
                q.add(next);
            }
        }

        return false;
    }
}