문제 출처

1. 문제설명

  • 문제 설명이 길어, 요약하겠다.
  • N*M 크기의 보드판이 있고, 각 칸에는 알파벳 문자가 하나씩 적혀있다.
  • 시작하는 격자의 알파벳을 기준으로 어떤 문자열을 만들 수 있는 경우의 수를 찾는다.
    • 어떤 문자열은 같은 게 다시 등장할 수 있다.
  • 문자열을 이어붙일 때는 상,하,좌,우,대각선 방향으로 1칸씩 이동가능하다.
  • Out of Map(OOM) 시 반대 방향으로 이동하게 된다.



2. 알고리즘 설계

  • DFS 문제라고 생각했다.
  • 문제를 읽어보면, target 값이 재등장할 가능성이 있다.
    • map으로 경우의 수를 저장해두면, DP의 효과가 있다.
  • 이 문제의 경우 OOM의 처리를 안하고, 환형으로 본다.
    • 현재 좌표값에서 다음 좌표값, x의 길이를 더하고 x의 길이로 나눠주면 된다.
    • 이렇게 하면 환형 처리를 if문 없이 할 수 있다.
    • nx = (x + dx[dir] + x_len) % x_len
  • 보드판의 최대 크기가 10, target의 최대 길이는 5이므로
  • 구할 수 있는 모든 경우를 전부 미리 구해 놓는 방식을 채택하였다.



3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

int n, m, k;
string target, board[10];
unordered_map<string, int> cnt;

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

void dfs(int y, int x, string s) {
    cnt[s]++;
    if(s.size() == 5) return;

    for(int dir=0; dir<8; dir++) {
        int ny = (y + dy[dir] + n) % n;
        int nx = (x + dx[dir] + m) % m;

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    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++)
            dfs(i, j, string(1, board[i][j]));

    while(k--) {
        cin >> target;
        cout << cnt[target] << '\n';
    }

    return 0;
}