[백준] 20166. 문자열 지옥에 빠진 호석

문제 링크

20166. 문자열 지옥에 빠진 호석

풀이 과정

DFS 탐색과 해시맵을 사용해 문제를 해결했습니다.

for (int i = 0; i < K; i++) {
    words[i] = br.readLine();
    hashMap.put(words[i], 0);
}

먼저 주어진 K개의 신의 좋아하는 문자열 각각을을 배열에 저장함과 동시에 해당 문자열을 아직 못찾았다는 의미의 0을 해시맵에 저장합니다.

for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        dfs(i, j, 1, String.valueOf(map[i][j]));
    }
}

맵을 돌며, dfs 메소드 를 호출해 새로운 문자열을 만들어봅니다.

static void dfs(int x, int y, int cnt, String s) {
    if (hashMap.containsKey(s)) hashMap.put(s, hashMap.get(s) + 1);

    if (cnt > 5) return;

    for (int d = 0; d < 8; d++) {
        int nx = x + dx[d], ny = y + dy[d];

        if (nx < 0) nx = N - 1;
        else if (nx > N - 1) nx = 0;
        if (ny < 0) ny = M - 1;
        else if (ny > M - 1) ny = 0;

        dfs(nx, ny, cnt + 1, s + map[nx][ny]);
    }
}

dfs 메소드 는 문자열을 이어붙이는 작업과 동시에 중간 과정 중 만들어진 문자열이 신이 좋아하는 문자열인지를 판별합니다.

• 파라미터로 입력받은 문자열 s 가 신이 좋아하는 문자열을 만족하면, 해당 개수를 1 증가시킵니다.
• 신이 좋아하는 문자열의 길이는 최대 5이므로, 문자열 길이가 5를 넘어가면 탐색을 멈춥니다.
• 8 방향에 존재하는 문자를 이어붙인 뒤, 다음 차례에서의 확인을 위해 dfs 메소드를 재귀 호출합니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    static int N, M, K;
    static char[][] map;
    static String[] words;
    static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1}, dy = {-1, 0, 1, -1, 1, -1, 0, 1};
    static HashMap<String, Integer> hashMap;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = stoi(st.nextToken());
        M = stoi(st.nextToken());
        K = stoi(st.nextToken());
        map = new char[N][M];
        words = new String[K];
        hashMap = new HashMap<>();

        for (int i = 0; i < N; i++) map[i] = br.readLine().toCharArray();
        for (int i = 0; i < K; i++) {
            words[i] = br.readLine();
            hashMap.put(words[i], 0);
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                dfs(i, j, 1, String.valueOf(map[i][j]));
            }
        }

        StringBuilder answer = new StringBuilder();
        for (String key : words) answer.append(hashMap.get(key) + "\n");
        System.out.println(answer);
    }

    static void dfs(int x, int y, int cnt, String s) {
        if (hashMap.containsKey(s)) hashMap.put(s, hashMap.get(s) + 1);

        if (cnt > 5) return;

        for (int d = 0; d < 8; d++) {
            int nx = x + dx[d], ny = y + dy[d];

            if (nx < 0) nx = N - 1;
            else if (nx > N - 1) nx = 0;
            if (ny < 0) ny = M - 1;
            else if (ny > M - 1) ny = 0;

            dfs(nx, ny, cnt + 1, s + map[nx][ny]);
        }
    }

    static int stoi(String s) { return Integer.parseInt(s); }
}