[백준]BJ_9202_Boggle

문제링크

문제

상근이는 보드 게임 "Boggle"을 엄청나게 좋아한다. Boggle은 글자가 쓰여 있는 주사위로 이루어진 4×4 크기의 그리드에서 최대한 많은 단어를 찾는 게임이다. 

상근이는 한 번도 부인을 Boggle로 이겨본 적이 없다. 이렇게 질 때마다 상근이는 쓰레기 버리기, 설거지와 같은 일을 해야 한다. 이제 상근이는 프로그램을 작성해서 부인을 이겨보려고 한다.

Boggle에서 단어는 인접한 글자(가로, 세로, 대각선)를 이용해서 만들 수 있다. 하지만, 한 주사위는 단어에 한 번만 사용할 수 있다. 단어는 게임 사전에 등재되어 있는 단어만 올바른 단어이다.

1글자, 2글자로 이루어진 단어는 0점, 3글자, 4글자는 1점, 5글자는 2점, 6글자는 3점, 7글자는 5점, 8글자는 11점이다. 점수는 자신이 찾은 단어에 해당하는 점수의 총 합이다.

단어 사전에 등재되어 있는 단어의 목록과 Boggle 게임 보드가 주어졌을 때, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어 사전에 들어있는 단어의 수 w가 주어진다. (1 < w < 300,000) 다음 w개 줄에는 단어가 주어진다. 단어는 최대 8글자이고, 알파벳 대문자로만 이루어져 있다. 단어 사전에 대한 정보가 모두 주어진 이후에는 빈 줄이 하나 주어진다.

그 다음에는 Boggle 보드의 개수 b가 주어진다. (1 < b < 30) 모든 Boggle은 알파벳 대문자로 이루어져 있고, 4줄에 걸쳐 주어진다. 각 Boggle의 사이에는 빈 줄이 하나  있다.

출력

각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개인 경우에는 사전 순으로 앞서는 것을 출력한다. 각 Boggle에 대해서 찾을 수 있는 단어가 적어도 한 개인 경우만 입력으로 주어진다.

---

정리

가로, 세로, 대각선 인접한 글자를 합하여 사전에있는 문자열을 만들 수 있는지 확인하는거
 찾은것중 -> 가장 긴 문자열과 찾은 단어수, 총점 출력

  점수
  길이 1~2 = 0점
  길이 3~4 = 1점
  길이 5 = 2점
  길이 6 = 3점
  길이 7 = 5점
  길이 8 = 11점
 
  각 보드에서 사전에 있는 단어를 찾는거임.

---

  풀이
  1. 사전에 있는 모든 문자열을 각 보드에서 찾고 답 갱신 
  2. 다음 번째 보드에서 찾고 답 기록 반복
 
  문자열을 뽑아서 찾을건데 어떻게 찾아야 효율적인가
  1. 첫 문자부터 차례대로 같아야하는 특성을 이용해서 풀이를 해본다.
  2. ICPC가 찾는거라면 첫번째를 찾아서 거기서부터 가로,세로,대각 방향으로 문자탐색한다.
      2-2. 그럼 보드에서 I의 위치를 찾고, 그 위치들에서 찾아보면 되겠군, 중간에 찾으면 그만하라고 알려줘야겠네
  3. 탐색한 문자는 두번째에 들어가야하니까 두번째랑 같은 문자열이 아닌경우는 리턴해야겠네
  4. 이게 빽트레킹이 맞나 싶다.
  5. 가지치기를 하면 되는구나
  6. 그럼 각 ?번째에 맞지 않은 문자들은 가지치기를 하므로 불필요한 연산을 줄일 수 있겠군요.

 결론은 찾을 문자열 시작위치 찾고 그 위치에서 DFS한다. 
  이걸로 풀어본다.

 

public class BJ_9202_Boggle {
    static int maxLen=-1, maxScore=0,findCnt;
    static String findString;
    // 상 하 좌 우 / 대각 : 좌상, 우상, 좌하, 우하 (8방향) 
    static int[] di = {-1, 1, 0, 0, -1, -1, 1, 1};
    static int[] dj = {0, 0, -1, 1, -1, 1, -1, 1};

    static final int SIZE = 4;
    static boolean isFind, visited[][];
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        String[] dataList = new String[N];
        for (int i = 0; i < N; i++) {
            String data = br.readLine();
            dataList[i] = data;
        }

        br.readLine(); // 빈줄 처리

        int boardCnt = Integer.parseInt(br.readLine());

        char[][][] board = new char[boardCnt][SIZE][SIZE];
        // 보드 입력

        for (int k = 0; k < boardCnt; k++) {

            for (int i = 0; i < SIZE; i++) {
                String s = br.readLine();
                for (int j = 0; j < SIZE; j++) {
                    board[k][i][j] = s.charAt(j);
                }
            }
            if(k < boardCnt-1){
                br.readLine(); // 빈줄 처리.
            }
        }


        // 각 보드에서 문자열 찾아볼것.
        for (int k = 0; k < boardCnt; k++) {
            // 각 보드마다 초기화
            maxLen=0;
            maxScore=0;
            findString="";
            findCnt=0;

            for (int i = 0; i <dataList.length ; i++) { // 문자열 리스트에서 찾을 문자열 뽑아오기.
                String cur = dataList[i];


                // 현재 보드에서 이 문자를 찾을 시작 위치를 불러온다.
                Queue<int[]> startXY = getStartXY(cur.charAt(0), board[k]);

                isFind = false;
                while(!startXY.isEmpty()){
                    int[] start = startXY.poll();



                    if(cur.length()==1){
                        isFind = true;
                        break;
                    }

                    visited = new boolean[SIZE][SIZE];
                    visited[start[0]][start[1]] = true; // 시작위치 방문처리.

                    findCur(cur, board[k],1,  start[0],start[1]);
                    if(isFind) break;
                }

                // 찾았다면 여기서 점수는 += | 길이는 더 길다면 갱신, 길이가 갱신되면 문자열 갱신.
                if(isFind){
                    findCnt++;
                    maxScore += getScore(cur); // 점수 갱신

                    if(maxLen <= cur.length()){
//                        System.out.println("findString = "+findString+" cur = "+cur);
                        if(maxLen == cur.length()){
                            findString = (findString.compareTo(cur) < 0 ) ? findString : cur;
                        }else{
                            findString = cur;
                        }
                        maxLen = cur.length();

                    }
                }
            }

            sb.append(maxScore+" "+findString+" "+findCnt+"\n");

        }
        System.out.println(sb);

    }



    private static void findCur(String target, char[][] board,int idx, int ci, int cj) {

        if(isFind) return;

        if(idx == target.length()){
            isFind=true;
            return;
        }

        // 8방향으로 탐색해본다.
        int ni,nj;
        for (int dir = 0; dir < 8; dir++) {
            ni = ci + di[dir];
            nj = cj + dj[dir];
//
//            System.out.println("찾을거 = "+target);
//            System.out.println(ni+", "+nj+" | idx = "+idx);
//            if(isIn(ni,nj)){
//                System.out.println(board[ni][nj]+" == "+target.charAt(idx));
//            }

            // 다음 자리의 문자와 찾은 문자가 같으면 넣어준다.
            if(isIn(ni,nj) && !visited[ni][nj] && board[ni][nj] == target.charAt(idx)){
                visited[ni][nj] = true;
                findCur(target,board,idx+1,ni,nj);
                visited[ni][nj] = false;
            }

        }


    }
    private static Queue<int[]> getStartXY(char c, char[][] chars) {
        Queue<int[]> q = new LinkedList<>();

        for (int i = 0; i < chars.length; i++) {
            for (int j = 0; j < chars.length; j++) {
                if(chars[i][j]==c) q.offer(new int[] {i,j});
            }
        }



        return q;

    }

    // * 길이 1~2 = 0점
// * 길이 3~4 = 1점
// * 길이 5 = 2점
// * 길이 6 = 3점
// * 길이 7 = 5점
// * 길이 8 = 11점
    private static int getScore(String cur) {
        int len = cur.length();
        if(len<=2){
            return 0;
        }else if (len<=4){
            return 1;
        } else if (len==5) {
            return 2;
        } else if (len==6) {
            return 3;
        } else if (len==7) {
            return 5;
        } else if (len==8) {
            return 11;
        }
        return 0;
    }

    private static boolean isIn(int ni, int nj){
        return 0<= ni && ni < SIZE && 0<= nj && nj < SIZE;
    }

}