[자바] 백준 14725 - 개미굴 (boj java)

문제 : boj14725

 

  알고리즘 분류를 봤다면 트라이를 봤을텐데, 필요없다. 그냥 그래프를 활용할 줄 안다면 풀 수 있다. 결국 다음의 예제 입력 1을

3
2 B A
4 A B C D
2 A C

이하의 그래프 처럼만 표현할 줄 알면 된다.

 

  각 정점은 먹이 이름과 간선으로 이루어진다. 그리고 동일한 depth에 동일한 이름이 존재할 경우엔 먹이 이름을 정점을 추가하지 않는다. 이것만 해주면 된다. 차후 출력 시 간선을 순서대로 순회해주며 출력하는 부분은 이하 코드처럼 매번 정렬을 해줘도 된다. 어차피 N이 최대 1000이므로, 딱히 해싱을 하지 않고 매번 모든 간선에 열결된 정점이름을 확인해도 문제 없다. 딱히 알고리즘 기법이 들어간게 없고, 그냥 그래프 자료구조 응용 문제로 상당히 좋은 문제인 것 같다.

 

 

코드 : github

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

class Food implements Comparable<Food> {
    String key;
    ArrayList<Food> edge;
    public Food(String key) {
        this.key = key;
        edge = new ArrayList<>();
    }

    @Override
    public int compareTo(Food o) {
        return this.key.compareTo(o.key);
    }
}
public class Main {
    StringBuilder ans = new StringBuilder();
    private void dfs(Food food, int depth) {
        Collections.sort(food.edge);
        for (Food next : food.edge) {
            for (int i = 0; i < depth; i++) ans.append('-').append('-');
            ans.append(next.key).append('\n');
            dfs(next, depth+1);
        }
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Food root = new Food(null);
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        while (n-->0) {
            st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());
            Food pt = root;
            for (int i = 0; i < k; i++) {
                String cur = st.nextToken();
                boolean isMatched = false;
                for (Food next : pt.edge) {
                    if (next.key.equals(cur)) {
                        pt = next;
                        isMatched = true;
                        break;
                    }
                }
                if (!isMatched) {
                    Food newFood = new Food(cur);
                    pt.edge.add(newFood);
                    pt = newFood;
                }
            }
        }
        dfs(root,0);
        System.out.println(ans);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}