[JAVA] 백준 20166번 : 문자열 지옥에 빠진 호석 - 테스트케이스 (2/16)

[20166번 : 문자열 지옥에 빠진 호석] - Gold4

접근 : dfs, 해시맵

 

테스트케이스 전부 통과 버전

---

[ 문제 ]

하루 종일 내리는 비에 세상이 출렁이고 구름이 해를 먹어 밤인지 낮인지 모르는 어느 여름 날

 

잠 들기 싫어 버티던 호석이는 무거운 눈꺼풀에 패배했다. 정신을 차려보니 바닥에는 격자 모양의 타일이 가득한 세상이었고, 각 타일마다 알파벳 소문자가 하나씩 써있다더라. 두려움에 가득해 미친듯이 앞만 보고 달려 끝을 찾아 헤맸지만 이 세상은 끝이 없었고, 달리다 지쳐 바닥에 드러누우니 하늘에 이런 문구가 핏빛 구름으로 떠다니고 있었다.

 

이 세상은 N행 M열의 격자로 생겼으며, 각 칸에 알파벳이 써있고 환형으로 이어진다. 왼쪽 위를 (1, 1), 오른쪽 아래를 (N, M)이라고 하자.

너는 아무 곳에서나 시작해서 상하좌우나 대각선 방향의 칸으로 한 칸씩 이동할 수 있다. 이 때, 이미 지나 왔던 칸들을 다시 방문하는 것은 허용한다.

 

1. 시작하는 격자의 알파벳을 시작으로, 이동할 때마다 각 칸에 써진 알파벳을 이어 붙여서 문자열을 만들 수 있다.
2. 이 곳의 신인 내가 좋아하는 문자열을 K 개 알려줄 터이니, 각 문자열 마다 너가 만들 수 있는 경우의 수를 잘 대답해야 너의 세계로 돌아갈 것이다.
3. 경우의 수를 셀 때, 방문 순서가 다르면 다른 경우이다. 즉, (1,1)->(1,2) 로 가는 것과 (1,2)->(1,1) 을 가는 것은 서로 다른 경우이다.

 

호석이는 하늘을 보고서 "환형이 무엇인지는 알려달라!" 며 소리를 지르니 핏빛 구름이 흩어졌다가 모이며 아래와 같은 말을 그렸다.

 

• 너가 1행에서 위로 가면 N 행으로 가게 되며 반대도 가능하다.
• 너가 1열에서 왼쪽으로 가면 M 열로 가게 되며 반대도 가능하다.
• 대각선 방향에 대해서도 동일한 규칙이 적용된다.

하늘에 아래와 같은 그림을 구름으로 그려줄 터이니 이해해 돕도록 하여라.

예를 들어서, 너가 (1, 1)에서 위로 가면 (N, 1)이고, 왼쪽으로 가면 (1, M)이며 왼쪽 위 대각선 방향으로 가면 (N, M)인 것이다

 

세상을 이루는 격자의 정보와, K 개의 문자열이 주어졌을 때, 호석이가 대답해야 하는 정답을 구해주도록 하자.

---

[ 입력 ]

첫번째 줄에 격자의 크기 N, M과 신이 좋아하는 문자열의 개수 K 가 주어진다.

 

다음에 N개의 줄에 걸쳐서 M개의 알파벳 소문자가 공백없이 주어진다. 여기서의 첫 번째 줄은 1행의 정보이며, N 번째 줄은 N행의 정보이다.

 

이어서 K개의 줄에 걸쳐서 신이 좋아하는 문자열이 주어진다. 모두 알파벳 소문자로 이루어져 있다.

---

[ 제한 ]

• 3 ≤ N, M ≤ 10, N과 M은 자연수이다.
• 1 ≤ K ≤ 1,000, K는 자연수이다.
• 1 ≤ 신이 좋아하는 문자열의 길이 ≤ 5
• 신이 좋아하는 문자열은 중복될 수도 있다.

---

[ 출력 ]

K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다.

# 예제 입력 1
3 3 2
aaa
aba
aaa
aa
bb

# 예제 출력 1
56
0

---

[ Code ]

import java.io.*;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.StringTokenizer;

public class Main {
    static int n, m, maxDepth;
    static char[][] arr;
    static int[] dy = {0, 0, -1, 1, 1, 1, -1, -1};
    static int[] dx = {-1, 1, 0, 0, 1, -1, 1, -1};
    static HashMap<String, Integer> map = new LinkedHashMap<>();
    static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        arr = new char[n][m];

        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < m; j++) {
                arr[i][j] = str.charAt(j);
            }
        }

        for (int i = 0; i < k; i++) {
            String str = br.readLine();
            map.put(str, 0);
            maxDepth = Math.max(maxDepth, str.length());
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                sb = new StringBuilder();
                sb.append(arr[i][j]);
                dfs(i, j);
            }
        }

        for (String str : map.keySet()) {
            bw.write(map.get(str) + "\n");
        }
        bw.close();
    }

    static void dfs(int y, int x) {
        String cur = sb.toString();

        if (cur.length() > maxDepth) return;

        if (map.containsKey(cur)) {
            map.put(cur, map.get(cur) + 1);
        }

        boolean flag = true;
        for (String str : map.keySet()) {
            if (str.startsWith(cur)) {
                flag = false;
                break;
            }
        }
        if (flag) return;

        for (int i = 0; i < 8; i++) {
            int moveY = (y + dy[i] + n) % n;
            int moveX = (x + dx[i] + m) % m;

            sb.append(arr[moveY][moveX]);
            dfs(moveY, moveX);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

16개의 테스트 케이스 중 2개밖에 통과하지 못했다 ㅜㅜ.

내가 접근한 방법은 다음과 같다.

 

1. 입력

-  char 배열을 채운다.

- 정답 문자열을 해시맵에 추가한다.

- 이때, 가장 긴 문자열을 체크해준다. (maxDepth)

 

2. dfs

- 방문했던 곳을 다시 방문해도 되므로 visited 배열은 사용하지 않았다.

- 현재 문자열이 maxDepth 보다 길어지면 return.

- 현재 문자열이 정답이라면 해시맵의 value+1 해준다.

- 중복된 문자열이 더 있을 수 있으므로 return하지 않는다. (정답 문자열 : aa -> 또 다른 정답 문자열 : aaa)

- 현재 문자열의 시작 문자가 정답 문자열에 없다면 return 한다. (현재 문자열 시작 문자 : a -> 정답 문자열에는 a로 시작하는 정답 문자가 없다.)

- 상, 하, 좌, 우, 좌상, 우상, 좌하, 우하 로 이동하면서 현재 문자열에 추가한다.

- 환형 배열이므로, 모듈러 연산으로 wrap-around 시킨다.