(C++) - 백준(BOJ) 20166번 : 문자열 지옥에 빠진 호석

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

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

dfs문제였습니다.

 

 

📕 풀이방법

k를 입력받을 때마다 dfs를 수행한다면 tle입니다. 따라서 전처리로 dfs 후 k를 입력받아야 합니다.

 

📔 입력 및 초기화

n,m,k 입력 후 문자열 배열 board에 적절히 입력받습니다.

 

📔 풀이과정

 1. n행 m열을 모두 돌며 board[i][j]를 시작점으로 dfs를 수행해 줍니다.

 

 2. dfs 수행 시 만든 문자열을 모두 map에 넣어줍니다. 해당 문자열의 value를 1씩 증가시킴으로써 경우의 수를 구할 수 있습니다.

 

📔 정답출력

k만큼 문자열을 입력받았을 때 map[문자열] 을 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
string board[11];
int n,m,k;
int dr[] = {-1,-1,-1,0,0,1,1,1};
int dc[] = {-1,0,1,-1,1,-1,0,1};

map <string,int> caseMap;
void dfs(int r, int c, int depth, string s){
    if(depth == 5) return;
    caseMap[s]++;
    for(int dir = 0; dir < 8; dir++){
        int nr = r + dr[dir];
        int nc = c + dc[dir];

        if(0 > nr) nr = n - 1;
        if(0 > nc) nc = m - 1;
        if(nr >= n) nr = 0;
        if(nc >= m) nc = 0;
        dfs(nr,nc,depth+1,s+board[nr][nc]);
    }
}

int main(){
    fastio;
    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 start = "";
            dfs(i,j,0,start + board[i][j]);
        }
    }

    while(k--){
        string s;
        cin >> s;
        cout << caseMap[s] << '\n';
    }
}