백준 g4 20166 문자열 지옥에 빠진 호석 c++

 

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

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

 

문제

N*M크기의 문자열 배열이 주어진다. 호석은 아무 곳에서나 시작해서 상하좌우+4개의 대각선 방향으로 한 칸씩 움직일 수 있다. 호석이 움직이는 길로 하나의 문자열을 만들 수 있다.

 

신이 좋아하는 K개의 문자열이 주어진다(K <= 1000, K의 길이 <=5). 각 K개의 문자열에 대해 호석이 만들 수 있는 경우의 수를 구해서 출력하기

 

호석은 왔던 길을 다시 돌아갈 수 있다.

 

풀이

해시 단원 문제인 건 알았지만 해시를 어디에 적용할 지 몰라 일단 그냥 dfs 구현으로 풀어보았다. 호석이 왔던 곳을 다시 되돌아 갈 수 있고 K의 길이가 5 밖에 안 되니 (depth가 5까지만 내려감) vis가 없어도 해볼만하다고 생각했음

 

그러나 78%에서 역시나 시간 초과가 걸렸고, 대체 어디서 해시를 써야할 지 감이 안 와서 다른 풀이들을 찾아봤다.

DFS를 하면서 말 그대로 만들 수 있는 모든 문자열의 경우의 수를 ++하며 진행한 것

 

기존의 풀이는

for K 문자열
	for i,j 시작점 고르기
    		dfs()

였지만 K개가 1000개나 되기 때문에 위의 풀이는 시간 초과가 걸릴 수 있음

 

신이 줄 수 있는 문자열의 종류가 26^5 = 약 2000만 개 정도이기 때문에 map으로 해도 메모리 초과가 나지 않으며, 한 번에가능한 모든 문자열을 다 구해놓으면 DFS를 한 번만 돌아도 되므로 시간 절약이 된다.

for i, j 시작점 고르기
	dfs
    
for K문자열
	map[K문자열] 출력

 

+) char to string

char[10]인 배열은 생성자로 바로 가능. ex string str(arr)

 

string + char는 가능

=> 한 글자짜리는 빈 string 생성 후 +=로 붙여주기

 

전체 코드

/*boj g4 20166 문자열 지옥에 빠진 호석*/
#include <iostream>
#include <unordered_map>
#define MAXN 12
using namespace std;

int N, M, K;
string board[MAXN];

int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

unordered_map<string, int> map;

void dfs(int x, int y, string str) {
    if (str.size() > 5) {
        return;
    }
    map[str]++;
    for (int dir = 0; dir < 8; dir++) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        // 범위 밖이면 조절
        if (nx < 0) nx += N;
        if (nx >= N) nx -= N;
        if (ny < 0) ny += M;
        if (ny >= M) ny -= M;

        dfs(nx, ny, str + board[nx][ny]);
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M >> K;

    for (int i = 0; i < N; i++) {
        cin >> board[i];
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            string str = "";
            str += board[i][j];
            dfs(i, j, str);
        }
    }

    string kStr;
    while (K--) {
        cin >> kStr;
        cout << map[kStr] << "\n";
    }
}

 

참고

https://alstj-success.tistory.com/107