[백준-1165,13502] 단어 퍼즐 (Trie,DFS,FTP)

Baekjoon 2020. 5. 19. 14:22

*답을 구하는 해법을 기술 하였고 실제 제출시 통과되는 풀이는 아닙니다.

*실제 제출시 통과되는 풀이로 업데이트 예정

문제 요약

백준에서 이 문제는 무려 다이아 문제이다. 소스 코드량에 제한이 있어 코드량 최적화가 필요한 문제이다.

대문자 알파벳이 하나씩 적혀있는 5x5의 보드와 단어 리스트 (사전)가 주어진다.

주어진 보드의 각 칸에서 8방향 탐색을 통해 사전에 있는 단어를 몇개 만들 수 있는지를 구하는 문제이다.

문제 풀이

문자열을 검색한다는 개념에서 Trie를 활용한 풀이를 기술한다.

다만 이 문제의 가장 큰 제약사항은

"소스 코드의 크기가 65536B를 넘을 수 없다"는 점이다.

제약사항을 봤을 때

이 문제를 풀기 위한 올바른 접근 방법은 코드안에 사전 데이터를 미리 넣어야 한다는 것이다.

주어진 사전 속의 단어의 개수는 24830개이고 이 텍스트 데이터들을 코드에 그대로 넣으면

이클립스 같은 경우 다음과 같은 컴파일 에러를 보게된다.

"The code of method makeDictionaryByTrie() is exceeding the 65535 bytes limit"

이것은 Java 코드를 돌려주는 JVM의 최대 메소드 사이즈가 64k로 지정이 되어 있어 이를 초과했다는 에러 메세지이다.

또한 사전 데이터를 그대로 넣으면 소스 코드가 20만~30만 바이트가 된다.

따라서 이 문제를 풀기 위해서는 주어진 사전 단어 데이터들을 제약사항에 맞게 최적화 해야하는 것이다.

본문에서는 소스 코드를 최적화 하지 않고 FTP 개념을 활용하여 원격에 있는 사전 데이터 파일을 요청 및 receive하여 추출한 뒤 구현한 Trie에 전부 등록한 후 dfs를 통해 답을 구하는 풀이를 기술한다.

Trie는 문자열의 집합을 표현하는 트리 형태의 자료구조이다.

Solution

1. 사전(Dictionary) 데이터를 소스 코드에 집어 넣지 않고 다운로드 url을 통해 파일 다운로드를 하여 내용물을 추출한다.

대회 사이트 혹은 백준 문제 하단의 다운로드 도메인 주소를 url로 지정해 준다.

https://contest.usaco.org/FEB09.htm

단어 파일의 형태는 Zip으로 압축되어 있어서 자바의 다음 라이브러리를 활용한다.

import java.util.zip.ZipEntry;

import java.util.zip.ZipInputStream;

24830개의 단어를 읽어 String[]에 저장 한 후 Trie에 등록한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

private static void getDictionaryAndsetTrie() throws UnknownHostException, IOException {
        URL url = new URL("https://d2gd6pc034wcta.cloudfront.net/data/1165.zip");
        StringBuilder sb = new StringBuilder();
        InputStream in = new BufferedInputStream(url.openStream(), 1024*4);
        ZipInputStream stream = new ZipInputStream(in);
        byte[] buffer = new byte[1024*4];
        ZipEntry entry;
        while ((entry = stream.getNextEntry()) != null) {
            int read;
            String data ="";
            while ((read = stream.read(buffer, 0, 1024*4)) >= 0) {
                data = new String(buffer, 0, read);
                sb.append(data);
                //System.out.println(data);
            }
        }
        wordlist = sb.toString().split("\n");//개행 문자로 스플리트
        for(String data : wordlist) Trie.insert(data); //트라이에 등록
    }    
Colored by Color Scripter

cs

2. Trie를 구성하는 각 노드는 26개(알파벳 개수) 짜리의 TrieNode 배열로 구성하였다.

아스키코드를 통해 현재 글자에서 다음 글자로 갈 수 있는 것인지 부모-자식 관계를 통해 확인하고 등록한다.

ABC라는 단어가 있다고 하자.

root에서 시작하여 한글자씩 파싱, 파스 트리를 구성한다.

1. root의 자식 26개 TrieNode 중 A가 null인지 확인. null 이라면 'A'-'A'(아스키) 인덱스에 TrieNode 생성.

2. 만들어진 A의 자식 26개 TrieNode중 B가 null인지 확인. null 이라면 'B'-'A' 인덱스에 TrieNode 생성.

3. 만들어진 B의 자식 26개 TrieNode중 C가 null인지 확인. null 이라면 'C'-'B' 인덱스에 TrieNode 생성 끝.

이후 AB라는 단어를 추가 등록할 때

1. root의 자식 26개 TrieNode 중 A가 null인지 확인. null 이아니므로 'A'-'A' 인덱스에 해당하는 자식 노드 확인

2. 확인된 A의 자식 26개 TrieNode 중 B가 null인지 확인. null이 아니므로 AB는 이미 Trie 자료구조에 존재하는 단어가 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

static class TrieNode{
        TrieNode[] children = new TrieNode[26];//26개의 알파벳 하나하나의 인덱스를 뜻하는 배열
    }
    static class Trie{ //트라이, 문자검색
        TrieNode root = new TrieNode(); //가장 루트는 빈문자열
        void insert(String word){//어떤 단어를 받아서 처리
            TrieNode current = root;
            for(int i=0;i<word.length();i++){//들어온 단어의 길이만큼 첫글자부터 확인
                int wordIndex = word.charAt(i)-'A'; //글자 알파벳의 인덱스
                if(current.children[wordIndex]==null){//글자 알파벳을 확인해 봤을 때 null이라는건 존재하지않는다는것
                    current.children[wordIndex] =new TrieNode();//없으니까 새로 생성해준다.
                }
                current = current.children[wordIndex];// 다음 레벨로 넘어가기 위해 생성된 글자가 현재 노드가 된다
            }
        }
    }
Colored by Color Scripter

cs

3. 구성한 트라이 노드를 통해 이제 문자를 검색하기 위해 5x5 보드를 dfs를 통해 탐색하여 단어가 존재하는지 확인한다.

24830개의 단어를 하나씩 보면서 첫번째 글자와 일치하는 칸에서 8방향 탐색을 통해 단어의 존재를 확인한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

private static void find(){
        System.out.println(wordlist.length);//단어개수
        for(int i=0;i<wordlist.length;i++){ //단어를 하나씩 봄.
            String data = wordlist[i];
            findFlag = false; //찾았으면 더 이상 볼 필요가 없기 때문에 발견 flag를 둠.
            for(int row=0;row<5;row++) {//퍼즐 탐색
                for(int col=0;col<5;col++){
                     //첫번째 글자가 같은 경우 
                    if(Trie.root.children[puzzle[row][col]-'A']!=null && data.charAt(0)==puzzle[row][col]){
                        visit[row][col] = true;
                        //트라이 노드를 줘서 자식을 직접 확인해봄
                        dfs(row,col,1,Trie.root.children[puzzle[row][col]-'A'],data); 
                        visit[row][col] = false;
                    }
                    if(findFlag) break;
                }
                if(findFlag) break;
            }
        }
    }
    private static void dfs(int row, int col, int depth, TrieNode current,String data){
        if(findFlag) return;
        if(depth==data.length() && findFlag==false){ 
         //길이가 같다면 dfs 탐색을 통해 단어를 찾았다는 것.
            answer++;
            findFlag = true;
            return;
        }
        if(depth < data.length()) {
            for(int dir=0;dir<8;dir++) {
                int nr = row+dr[dir];
                int nc = col+dc[dir];
                if(rangeCheck(nr,nc)){
                     //자식이 존재할 때
                    if(visit[nr][nc]==false && current.children[puzzle[nr][nc]-'A']!=null && data.charAt(depth)==puzzle[nr][nc]) {
                        visit[nr][nc] = true;
                        dfs(nr,nc,depth+1,current.children[puzzle[nr][nc]-'A'],data);
                        visit[nr][nc] = false;
                    }
                }
            }
        }
    }
    private static boolean rangeCheck(int nr, int nc) { //영역체크
        if(nr>=0 && nr<5 && nc>=0 && nc<5) return true;
        return false;
    }
Colored by Color Scripter

cs

Full code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.net.URL;
import java.net.UnknownHostException;
import java.util.StringTokenizer;
import java.util.zip.ZipEntry;
import java.util.zip.ZipInputStream;
 
 
public class Main{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static char[][] puzzle = new char[5][5];
    static boolean[][] visit = new boolean[5][5];
    static StringTokenizer st;
    static int[] dr = {-1,-1,0,1,1,1,0,-1};
    static int[] dc = {0,1,1,1,0,-1,-1,-1}; //8방향
    static int answer;
    static String[] wordlist;
    static Trie Trie = new Trie();
    static boolean findFlag;
    static class TrieNode{
        TrieNode[] children = new TrieNode[26];//26개의 알파벳 하나하나의 인덱스를 뜻하는 배열
    }
    static class Trie{ //트라이, 문자검색
        TrieNode root = new TrieNode(); //가장 루트는 빈문자열
        void insert(String word){//어떤 단어를 받아서 처리
            TrieNode current = root;
            for(int i=0;i<word.length();i++){//들어온 단어의 길이만큼 첫글자부터 확인
                int wordIndex = word.charAt(i)-'A'; //글자 알파벳의 인덱스
                if(current.children[wordIndex]==null){//글자 알파벳을 확인해 봤을 때 null이라는건 존재하지않는다는것
                    current.children[wordIndex] =new TrieNode();//없으니까 새로 생성해준다.
                }
                current = current.children[wordIndex];// 다음 레벨로 넘어가기 위해 생성된 글자가 현재 노드가 된다
            }
        }
    }
    public static void main(String[] args) throws IOException{
        getDictionaryAndsetTrie();
        setData();
        if(wordlist!=null) find();
        System.out.println(answer);
    }
    private static void find(){
        //System.out.println("다운로드하여 추출한 단어의 개수 "+wordlist.length);//단어개수
        for(int i=0;i<wordlist.length;i++){
            String data = wordlist[i];
            findFlag = false;
            for(int row=0;row<5;row++) {//퍼즐 탐색
                for(int col=0;col<5;col++){
                    if(Trie.root.children[puzzle[row][col]-'A']!=null && data.charAt(0)==puzzle[row][col]){//갈 수 있으면 
                        visit[row][col] = true;
                        dfs(row,col,1,Trie.root.children[puzzle[row][col]-'A'],data); //트라이 노드를 줘서 자식을 직접 확인해봄
                        visit[row][col] = false;
                    }
                    if(findFlag) break;
                }
                if(findFlag) break;
            }
        }
    }
    private static void dfs(int row, int col, int depth, TrieNode current,String data){
        if(findFlag) return;
        if(depth==data.length() && findFlag==false){
            answer++;
            findFlag = true;
            return;
        }
        if(depth < data.length()) {
            for(int dir=0;dir<8;dir++) {
                int nr = row+dr[dir];
                int nc = col+dc[dir];
                if(rangeCheck(nr,nc)){
                    if(visit[nr][nc]==false && current.children[puzzle[nr][nc]-'A']!=null && data.charAt(depth)==puzzle[nr][nc]) {
                        visit[nr][nc] = true;
                        //자식이 존재할 때 
                        dfs(nr,nc,depth+1,current.children[puzzle[nr][nc]-'A'],data);
                        visit[nr][nc] = false;
                    }
                }
            }
        }
    }
    private static boolean rangeCheck(int nr, int nc) {
        if(nr>=0 && nr<5 && nc>=0 && nc<5) return true;
        return false;
    }
    private static void getDictionaryAndsetTrie() throws UnknownHostException, IOException {
        /*
         * "https://d2gd6pc034wcta.cloudfront.net/data/1165.zip"
         * "/TESTDATA/coggle.zip"
         * 66.113.2.158
         * 
         */
        
        URL url = new URL("https://d2gd6pc034wcta.cloudfront.net/data/1165.zip");
        //URL url = new URL("http://66.113.2.158/TESTDATA/coggle.zip");
        StringBuilder sb = new StringBuilder();
        InputStream in = new BufferedInputStream(url.openStream(), 1024*4);
        ZipInputStream stream = new ZipInputStream(in);
        byte[] buffer = new byte[1024*4];
        ZipEntry entry;
        while ((entry = stream.getNextEntry()) != null) {
            int read;
            String data ="";
            while ((read = stream.read(buffer, 0, 1024*4)) >= 0) {
                data = new String(buffer, 0, read);
                sb.append(data);
                //System.out.println(data);
            }
        }
        wordlist = sb.toString().split("\n");
        for(String data : wordlist) Trie.insert(data);
    }
    private static void setData() throws IOException {
        for(int row=0;row<5;row++) {
            st = new StringTokenizer(br.readLine());
            for(int col=0;col<5;col++) {
                puzzle[row][col] = st.nextToken().charAt(0);
            }
        }
    }    
}
 
Colored by Color Scripter

cs