[자바] 백준 6755 - Who is taller? (boj java)

문제 : boj6755

 

  입력으로 들어온 M개의 x가 y보다 크다는 정보를 가지고, p가 q보다 큰지(yes) 혹은 q가 p보다 큰지(no) 혹은 검증이 불가한지(unknown) 알아낼 수 있어야 한다. 그래프로 생각해보자.

 

  우선 각 N명의 사람을 정점으로 하고, 간선을 x에서 y로 (즉 큰 사람에서 작은사람쪽으로) 하는 방향 그래프를 생각해보자. 그럼 간단히 p에서 q로 간선을 타고 이동이 가능하다면 p가 q보다 큰게 된다. 반대로 q에서 p로 간선을 타고 이동이 가능하다면 q가 p보다 큰게 된다. 둘 다 불가했다면 검증이 불가하다. 지문의 'you always compare correctly'에 따라 사이클이 생긴다거나, p에서 q로도 갈 수 있고 q에서 p로도 갈 수 있는 상황은 그냥 문제가 틀린셈이 되니 생각하지 않아도 된다.

 

  예제 입력 1 을 생각해보자.

10 3
8 4
3 8
4 2
3 2

위에서 얘기한 방식대로 방향그래프로 만들면 아래와 같다. 그리고 3에서 출발해 2로 탐색이 가능하므로 (bfs, dfs 뭘 써도 상관없다), yes가 답이 된다. 다른 예로 [p=8, q=2]도 마찬가지로 yes, [p=4, q=3]이라면 no (4->3은 불가하지만 3->4는 가능하므로), [p=6, q=2] 라면 unknown이 된다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    private ArrayList<Integer>[] edges;
    private boolean[] v;
    private boolean dfs(int s, int e) {
        if (s == e) return true;
        for (int next : edges[s]) {
            if (v[next]) continue;
            v[next] = true;
            if (dfs(next, e)) return true;
        }
        return false;
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        edges = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) edges[i] = new ArrayList<>();
        while (m-->0) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            edges[x].add(y);
        }
        st = new StringTokenizer(br.readLine());
        int p = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());
        v = new boolean[n+1];
        v[p] = true;
        if (dfs(p, q)) {
            System.out.println("yes");
            return;
        }
        v = new boolean[n+1];
        v[q] = true;
        if (dfs(q, p)) {
            System.out.println("no");
            return;
        }
        System.out.println("unknown");
    }

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