[PS/BOJ] 20166번. 문자열 지옥에 빠진 호석 - C++[cpp]

문제

 

접근

탐색을 하면서 현재 구성하고 있는 문자열이 신이 좋아하는 문자열인지를 체크해주면 된다.

이 문제의 특징이라면, 지나왔던 칸에 다시 방문할 수 있다는 것. 그리고 비교 대상이 되는 문자열의 길이가 5이하로 매우 짧다는 점이다.

 

이 문제를 살펴보고 탐색까지 떠올렸으면 BFS? DFS? 를 생각해볼 것이다. 이런 문제에선 현재 구성하고 있는 문자열로 신이 좋아하는 문자열을 만들 수 없는 경우에는 탐색을 멈추고, 아니면 탐색을 계속하도록 DFS를 생각해볼 수 있다.

이렇게 접근한다면 구현하려고 생각해본다면

 

1. 모든 문자열의 substring, 그리고 신이 좋아하는 문자열에 모두 포함되면 되면 count를 증가

2. substring에만 속하면 이어서 탐색

3. substring에만 속한다면 탐색 종료

 

 

하지만 문제 조건에서 문자열의 길이가 5 이하이다. 아무리 최악이여도 탐색의 깊이가 5를 넘지 않기 때문에, 단순히 현재 구성하고 있는 문자열이 신이 좋아하는 문자열들 중에 존재하는지만 체크해주면 된다.

 

사실 문제의 아이디어는 굉장히 간단하지만, 이 문제를 글로 적은 이유는 따로 있다.

보통 탐색 문제에서 대각선 이동을 잘 다루지 않기도 하고, 이 문제에서는 8방향 이동 + 특정 조건에서의 이동 로직이 존재한다.

 

처음에는 8방향 케이스와, 특정 조건에 대한 케이스를 모두 분류해서 코드를 작성했는데, 더 좋은 구현 방법이 존재해서 이 글을 작성하게 됬다.

 

보통 상하좌우 이동에서는 다음과 같이 구현을 한다.

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

for (int i = 0; i < 4; i++) {
	int nx = curX + dx[i];
	int ny = curY + dy[i];
}

 

이제 8방향 이동을 잘 생각해보자.

 

x축을 기준으로 {11시, 12시, 1시 이동}, {3시, 9시 이동}, {5시, 6시, 7시 이동} 이렇게 분류하면 {+1, 0, -1}이 된다.

y축을 기준으로 {11시, 9시, 7시 이동}, {12시, 6시 이동}, {5시, 3시, 1시 이동} 이렇게 분류하면 {+1, 0, -1}이 된다.

 

여기서 멈춰있는 경우를 추가하면 

 

x축을 기준으로 {11시, 12시, 1시 이동}, {3시, 멈춤, 9시 이동}, {5시, 6시, 7시 이동} 이렇게 분류하면 {+1, 0, -1}이 된다.

y축을 기준으로 {11시, 9시, 7시 이동}, {12시, 멈춤, 6시 이동}, {5시, 3시, 1시 이동} 이렇게 분류하면 {+1, 0, -1}이 된다.

 

이에 대해 2중 for문을 돌리고, 멈춘 경우만 continue로 제외해주면 8방향 이동을 모두 체크할 수 있다.

 

for (int dx = -1; dx <= 1; dx++) {
        for (int dy = -1; dy <= 1; dy++) {
            if(dx == 0 && dy == 0) continue;
            int nx = (x + dx + n) % n;
            int ny = (y + dy + m) % m;
        }
    }​​

또한 이 문제의 특별한 경우 (1, 1), (1, ~) (~, m), (n, m), (n, ~), (~, m) 의 이동을 모듈러 연산을 통해서 깔끔히 처리해줄 수 있다. 

 

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

int n, m, k;
char arr[11][11];
string target[1001];
unordered_map<string, int> hm;

void DFS(int x, int y, string cur_string) {
    if (hm.contains(cur_string)) hm[cur_string] += 1;
    if (cur_string.length() >= 5) return;
    
    // 8 방향 이동
    for (int dx = -1; dx <= 1; dx++) {
        for (int dy = -1; dy <= 1; dy++) {
            if(dx == 0 && dy == 0) continue;
            int nx = (x + dx + n) % n;
            int ny = (y + dy + m) % m;
            DFS(nx, ny, cur_string + arr[nx][ny]);
        }
    }
}

int main(void) {
    cin.tie(0)->sync_with_stdio(false);
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) cin >> arr[i][j];
    }

    for (int i = 0; i < k; i++) {
        cin >> target[i];
        hm[target[i]] = 0;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) DFS(i, j, string(1, arr[i][j]));
    }

    for (int i = 0; i < k; i++) cout << hm[target[i]] << '\n';
}