[자바] 백준 1897 - 토달기 (boj java)

문제 : boj1897

 

  문제에서 제시된 로직대로 진행한다면, 항상 L 길이의 단어는 L+1 길이의 단어가 된다. 또한 이 때, L 길이의 단어에 있는 각 문자의 순서는 L+1 길이의 단어에서 나타나는 문자의 순서와 동일하면서, 딱 하나의 문자만 추가될 것이다. 그렇다면 현재 L길이의 단어를 보고 있을 때, L+1 길이의 단어들 중 이동 가능한 문자로 진행을 하는걸 더이상 진행할 수 없을때까지 해보면 될 것이다. 즉, 그렇게 안생겼지만 bfs나 dfs로 풀면 된다.

 

  간선은 [L 길이의 문자 A] -> [A와 문자 순서까지 생각했을 때, 1개의 문자만 추가된 문자 B] 와 같이 생성하면 될 것이다.

  미리 입력을 받으면서 글자의 길이에 따라 나누어두면 훨씬 효율적으로 진행할 수 있다. 또한 String이므로 방문 체크는 HashSet<String> 으로 처리할 수 있다(길이에 따라 나누어두면, 이 문제의 경우 방문체크를 별도로 하지 않아도 충분히 통과 가능하다).

 

  사실 아이디어만 잘 떠올랐다면, 어려울 수 있는 부분은 L길이의 문자에서 L+1 길이의 문자로 간선을 생성하는 과정 뿐이다. 내 경우엔 두 문자에 각각 포인터를 두고 (코드의 i, j) 서로 다른 문자가 1개를 초과하면 더이상 진행하지 않는 식으로 간선을 찾았다. 이 부분은 코드를 참고해보면 될 것 같다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int d = Integer.parseInt(st.nextToken());
        String s = st.nextToken();
        ArrayList<String>[] arr = new ArrayList[81];
        for (int i = 4; i <= 80; i++) arr[i] = new ArrayList<>();
        while (d-->0) {
            String cur = br.readLine();
            if (cur.length()<=3) continue;
            arr[cur.length()].add(cur);
        }
        Queue<String> q = new ArrayDeque<>();
        q.add(s);
        String answer = null;
        HashSet<String>[] hs = new HashSet[81];
        for (int i = 4; i <= 80; i++) hs[i] = new HashSet<>();
        while (!q.isEmpty()) {
            String cur = answer = q.poll();
            for (String next : arr[cur.length()+1]) {
                if (hs[next.length()].contains(next)) continue;
                int defCnt = 0;
                for (int i = 0, j = 0; i < cur.length() && j < next.length() && defCnt <= 1; ) {
                    if (cur.charAt(i) != next.charAt(j)) {
                        defCnt++;
                        j++;
                    } else {
                        i++;
                        j++;
                    }
                }
                if (defCnt <= 1) {
                    q.add(next);
                    hs[next.length()].add(next);
                }
            }
        }
        bw.write(answer);
        bw.flush();
    }

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