[자바] 백준 25601 - 자바의 형변환 (java)

 문제 : boj25601

---

 

필요 알고리즘 개념

• 그래프 탐색 (bfs, dfs)
  
  • 그래프 탐색을 할 수 있어야 한다. bfs, dfs 등
• 해시를 사용한 집합과 맵
  
  • String에 대한 간선 표현을 위해 HashMap 등의 자료구조를 사용할 수 있어야 한다.

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

 

---

 

풀이

  이게 뭔가 복잡해보일 수 있는데, 결국 그냥 그래프 정점과 간선이 주어지고 특정 지점에서 다른 지점으로 그래프 탐색이 가능하냐고 묻는 문제이다. 입력으로 주어진 N-1개의 A에서 B로 간선을 가지는 방향그래프(Directed Graph)로 생각해보자. 예제 입력 2의 경우 다음과 같이 그릴 수 있다.

 

  그리고 마지막줄에 주어진 두 클래스명 X, Y에 대해 X -> Y로 탐색이 가능하거나, Y -> X로 탐색이 가능한지 보면 된다. 각각 Upcasting과 Downcasting이 가능한지 보는 것이다. 예제 입력 2의 경우엔 number->integer로는 불가하지만, integer->number로는 가능하므로 1이 답이 된다.

 

  그럼 어떻게 풀었는지 알았으니 이제 클래스명의 String을 정점으로 가지고, String 끼리의 간선을 연결할 방법만 찾으면 된다. 별도 클래스로 만들어도 되지만 String 자체로 처리하려면 HashMap<String, ArrayList<String>> 정도의 자료구조를 사용하면 적당하다. A->B의 간선 정보에 대해 A가 HashMap의 key에 해당하고, B는 value의 List에 들어가는 형태이다. 그럼 이후 그래프 탐색은 알고있는 그래프 탐색(bfs, dfs 등) 아무거나 사용해주면 된다. 코드에서 'System.out.println(bf(a, b) || bf(b, a) ? 1 : 0);' 부분에 bf(a, b)와 bf(b, a)가 위에서 말한 X->Y 또는 Y->X를 의미한다.

 

  .. 는 쓰고보니 입력에서 '트리' 라고 구조를 고정했다. 그럼 HashMap<String, String> 으로 가능하다. 당연히 위처럼 ArrayList를 쓰는게 더 큰 개념이므로 별 문제 없다.

---

 

코드 : github

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

public class Main {
    HashMap<String, ArrayList<String>> edges;

    private boolean bf(String cur, String ed) {
        if (cur.equals(ed)) {
            return true;
        }
        if (edges.get(cur) == null)
            return false;
        for (String next : edges.get(cur)) {
            if (bf(next, ed))
                return true;
        }
        return false;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        edges = new HashMap<>();
        for (int i = 0; i < n-1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String a = st.nextToken();
            String b = st.nextToken();
            if (!edges.containsKey(a)) {
                edges.put(a, new ArrayList<>());
            }
            edges.get(a).add(b);
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        String a = st.nextToken();
        String b = st.nextToken();
        System.out.println(bf(a, b) || bf(b, a) ? 1 : 0);
    }

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