[BOJ20166] 문자열 지옥에 빠진 호석 (완전탐색, DFS)

 

 

---

문제 링크

https://www.acmicpc.net/problem/20166

20166번: 문자열 지옥에 빠진 호석

 

문제 풀이

중복 방문을 허용하고, 상하좌우 대각선(8개 방향) 방향으로 이동하여 문자열을 만듦

 

참고. 시간 복잡도

행 * 열 * (8방향으로 이동^최대 단어 길이 5)
= 100 * (8^5) 
= 3,276,800 (1초안에 수행 가능)

 

참고. 방향 이동 관련하여 ( 3 x 3 )

(0, 0) 좌표에서 아래 대각선 방향으로 이동할 경우 맵의 범위를 벗나게 될 것이다

(-1, -1)	(-1, 0)	(-1, 1)
(0, -1)	시작	(0, 1)
(1, -1)	(1, 0)	(1, 1)

문제에 주어진 조건에 따라 아래 같이 이동하면 되었다.

(-1, 1) ->  (N - 1, 1) 로 이동 

(1, -1) -> (1, M - 1) 로 이동

 

 

고쳐야 할 부분

- 처음 풀이시 "신이 좋아하는 문자열"별로 매번 완전 탐색을 하도록 구현하여 '시간 초과' 발생 ( 3276800 * 1000개, 1억 초과)

  전처리(3,276,800번) 후 값 호출을 할 경우 O(1)만큼 걸리므로, 완전 탐색 문제 풀이시 주의 하기 (조합, 순열 등등) 

- 적절한 자료 구조 선택 못함 

  카운팅을 셀 경우 HashMap 자료구조를 사용하도록 하자

- 재귀 함수 호출 시 종료 조건에 주의 하자

  문제에서 K가 '신이 좋아하는 문자열의 개수' 인데, '신이 좋아하는 문자열의 길이'로 착각해서 메모리 초과 발생(문제 잘 읽기)

   

 

제출 코드

import java.util.*;
import java.io.*;

public class Main {
	static StringBuilder sb = new StringBuilder();

    static int N, M, K;
    static char[][] wordMatrix;
    static List<String> queries = new ArrayList<>();

    static Map<String, Integer> wordMap = new HashMap<>();

    static int[][] DIR = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}, {1, -1}, {-1, 1}, {1, 1}, {-1, -1}};

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); // 행
        M = Integer.parseInt(st.nextToken()); // 열
        K = Integer.parseInt(st.nextToken()); // 신이 좋아하는 문자 개수

        wordMatrix = new char[N][M];
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            char[] words = st.nextToken().toCharArray();
            for(int j = 0; j < M; j++) {
                wordMatrix[i][j] = words[j];
            }
        }

        for(int i = 1; i <= K; i++) {
            queries.add(br.readLine()); // 신이 좋아하는 문자열
        }
    }

    static void rec(int x, int y, int len, String word) {
        if(wordMap.containsKey(word)) {
            wordMap.put(word, wordMap.get(word) + 1);
        } else {
            wordMap.put(word, 1);
        }

        if(len == 5) return; // 실수* K 개 줄에 단어가 주어졌지 길이 K라고 하진 않음

        for(int i = 0; i < 8; i++) {
            int dx = (x + DIR[i][0]) % N; // N 이상이면 0으로 
            int dy = (y + DIR[i][1]) % M; // M 이상이면 0으로

            if(dx < 0) dx += N; // dx = -1 일때 N - 1로 이동
            if(dy < 0) dy += M; // dy = -1 일때 M - 1로 이동 

            rec(dx, dy, len + 1, word + wordMatrix[dx][dy]);
        }
    }

    static void pro() {
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                rec(i, j, 1, wordMatrix[i][j] + "");
            }
        }

        for(String query : queries) {
            sb.append(wordMap.getOrDefault(query, 0)).append("\n");
        }

        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
}