[자바] 백준 25498 - 핸들 뭘로 하지 (java)

 문제 : boj25498

---

 

필요 알고리즘 개념

• 그리디 알고리즘 
  • 각 트리 깊이마다 사전상 마지막에 오는 문자를 택하는 규칙을 세워야 한다.
• bfs, dfs
  
  • 트리를 탐색하기 위해 bfs 혹은 dfs를 사용해야 한다.

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

 

---

 

풀이

  대회 당시에 규칙은 맞게 세워놓고 구현을 침착하게 안하다보니 엄청 틀렸었다 ㅠ.

 

  어차피 트리이니 사이클이 없고, 루트 노드도 주어졌으므로 루트노드부터 시작해서 리프노드까지 내려가면서 모든 경우의 수를 보면 어떨까? 물론 시간내에 통과할 수 없다.

 

  그리디 전략을 취해서 매번 간선들 중 최선의 선택(사전상 가장 마지막에 오는 문자 선택)을 해주면 어떨까? 이 때, 해당 정점의 깊이가 곧 결과 문자열에서의 인덱스 위치가 될 것이므로 깊이 기준으로 가장 큰걸 선택해주면 된다. dfs로 진행할 시에는 해당 깊이에 해당하는 결과 문자열이 자신보다 크다면 무시하는 백트래킹을 적용하면 된다. bfs로는 각 깊이마다 수평적으로 진행될 것이므로 더 효율적으로 짤 수 있다. 이하 풀이는 bfs를 통한 풀이이다.

 

  bfs 기준으로 로직은 아래와 같다.

1. 루트노드를 큐에 넣는다.

2. 큐가 빌때까지 전부 빼면서, 해당 정점에서 진행 가능한 정점 중 사전순으로 가장 마지막에 오는 후보들을 따로 저장해둔다.

3. 후보들은 모두 동일한 문자에 해당하는 정점들로, 해당 깊이에서의 문자열이 확정되었으므로 결과 문자열에 붙여준다. 그리고 후보들을 다시 큐에 넣는다.

4. 2~3을 후보들이 더이상 생기지 않을 때 까지 반복한다.

 

---

 

  아래와 같은 트리가 있을 시 진행 과정을 살펴보자.

 

 

1. 루트를 큐에 넣는다. 루트가 첫 번째 글자임은 확실하므로 정답문자열에 추가해준다.

 

 

2. 진행 가능한 d, b, e, e 중에 사전상 마지막은 e 이므로 e 두개로만 진행한다. 2번째 정답 문자는 e로 확정되었다.

 

3. 다음 진행 가능한 곳은 c,b,b,c 이고 이 중 가장 큰건 c 이므로 c로 진행한다. 마찬가지로 정답 문자도 추가한다.

 

4. 진행 가능한 곳은 a 하나이므로 다음 진행은 a로 간다. 같은 깊이에 u,g,d,h,z 다양하지만 그 이전 문자가 더 작으므로 모두 의미가 없다.

 

 

5. 더이상 진행할 곳이 없으므로 정답은 'aeca'가 된다.

 

---

 

코드 : github

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

public class Main {
    int n;
    String s;
    ArrayList<Integer>[] edges;

    private char getChar(int idx) {return s.charAt(idx-1);}
    private StringBuilder getAnswer() {
        StringBuilder sb = new StringBuilder();
        ArrayList<Integer> arr = new ArrayList<>();
        boolean[] v = new boolean[n+1];
        arr.add(1);
        v[1] = true;
        sb.append(getChar(1));
        while (!arr.isEmpty()) {
            ArrayList<Integer> validNodes = null;
            char max = '\0';
            for (int cur : arr) {
                for (int next : edges[cur]) {
                    if (v[next]) continue;
                    char charOfNext = getChar(next);
                    if (max > charOfNext) continue;
                    if (validNodes == null || max < getChar(next)) {
                        validNodes = new ArrayList();
                        max = getChar(next);
                    }
                    validNodes.add(next);
                }
            }
            if (validNodes == null) break;

            sb.append(max);
            ArrayList<Integer> tmp = new ArrayList<>();
            for (int next : validNodes) {
                v[next] = true;
                tmp.add(next);
            }
            arr = tmp;
        }
        return sb;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        s = br.readLine();
        edges = new ArrayList[n+1];
        for (int i = 0; i <= n; i++) edges[i] = new ArrayList<>();
        for (int i = 1; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            edges[a].add(b);
            edges[b].add(a);
        }
        System.out.println(getAnswer());
    }

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