백준 20166. 문자열 지옥에 빠진 호석 (해시)

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

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

정사각형 4개를 이어 붙인 도형(테트로미노)를 회전, 대칭 시켜 보드(입력으로 받음) 위에 놓는다. 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력.

백준 18808 스티커붙이기와 비슷하게 구현하였다. 

못풀어서 https://www.acmicpc.net/problem/20166 코드를 참고했다. 

 

1. 특징

1) 백트래킹...? 재귀...? dfs...?

2) 해시

 

2. 삽질 포인트

1) 처음에 아래와 같은 코드로 작성했다. 문자열을 입력받으면, 각 좌표마다 돌면서 갈 수 있는 8가지 경우(상하좌우, 대각선 4가지)를 백트래킹했다. 그랬더니 시간초과가 남. -> 계산해보면: 10^3(k값) * 8^4(5자리를 만들 경우의 수) * 10^2( 3 <= n, m <= 10) = 4억~ = 4초..

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

int n, m, k;
string board[12];
int dx[8] = {0, 0, -1, 1, 1, 1, -1, -1};
int dy[8] = {-1, 1, 0, 0, -1, 1, -1, 1};
int arr[8];
string que;
int ans;
int nx;
int ny;
bool checkfunc(int x, int y, int cur, int i)
{
    nx = (x + dx[i] + n) % n;
    ny = (y + dy[i] + m) % m;

    if(board[nx][ny] != que[cur]) return false;
    else return true;
}

void func(int cur, int x, int y)
{
    if(cur == k)
    {
        ans+=1;
        return;
    }

    if(cur == 0)
    {
        if(board[x][y] != que[0]) return;
        else func(cur + 1, x, y);
    }
    else
    {
        for(int i = 0; i < 8; i++)
        {
            if(checkfunc(x, y, cur, i))
            {
                arr[cur] = i;
                func(cur + 1, 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 num = 0; num < k; num++)
    {
        cin >> que;
        ans = 0;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
       
                func(0, i, j);
            }
        }
        cout << ans << '\n';
    }  
}

 

3. 구현 포인트

1) 환형형태

int nx = (x + dx[dir] + n) % n;
int ny = (y + dy[dir] + m) % m;

2) 정답 string값을 받기 전에, 만들어질 수 있는 모든 string 배열을 map으로 갖고있는다. -> 연산 대략 409600번, 시간초과 x

 

4. 코드 

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

int n, m, k;
string board[12];
int dx[8] = {0, 0, -1, 1, 1, 1, -1, -1};
int dy[8] = {-1, 1, 0, 0, -1, 1, -1, 1};
unordered_map<string, int> cnt;

void func(int x, int y, string s)
{
    cnt[s]++;
    if(s.size() == 5) return;
    for(int dir = 0; dir < 8; dir++)
    {
        int nx = (x + dx[dir] + n) % n;
        int ny = (y + dy[dir] + m) % m;

        func(nx, ny, s + 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++)
        {
            func(i, j, string(1, board[i][j]));
        }
    }

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