2186번 - 문자판

2024-05-07

#C++#백준

문제 링크

문제 풀이 시간 : 1시간

문제 요약

•
알파벳 문자가 한칸에 하나씩 적혀있는 NxM크기의 문자판이 있다.

•
임의의 칸에서 시작하여 상하좌우 K개의 칸까지 이동하며 문자를 모은다.

•
반드시 한 칸 이상 이동하며, 같은 자리에 머물 수 없다.

•
같은 칸을 여러 번 방문할 수 있다.

•
주어진 단어를 만들 수 있는 경우의 수를 모두 구하라.

문제 풀이

요즘 계속 자바로 코딩을 했더니 C++을 까먹을까 싶어서 오랜만에 C++로 문제를 풀어보았다.

문제를 보자마자 이승현의 특기인 맨 땅에 헤딩을 시전해서 DFS로 바로 풀기 시작했다.

초기 코드

Java

#include <iostream>
#include <string>

#define MAXINT 100
using namespace std;

char arr[MAXINT][MAXINT];
int n, m, k, sum = 0, dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
string input;

void find(int idx, int x, int y) {
    if (idx >= input.length()) {
        sum++;
        return;
    }
    for (int i = 1; i <= k; i++) {
        for (int j = 0; j < 4; j++) {
            int tx = x + dir[j][0] * i;
            int ty = y + dir[j][1] * i;
            if (tx < 1 || tx > n || ty < 1 || ty > m)
                continue;
            if (arr[tx][ty] == input[idx]) {
                find(idx + 1, tx, ty);
            }
        }
    }
}

int main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            cin >> arr[i][j];
    }
    cin >> input;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (arr[i][j] == input[0])
                find(1, i, j);
        }
    }
    cout << sum;

}

얼레?

이렇게 했더니 통과하는 듯 싶다가 시간 초과가 나왔다.

역시 골드3 문제라서 그런지 만만하게 풀 수 있는 문제는 아니었던 것 같다.

새로운 풀이법을 생각하다가 결국 포기하고 힌트를 찾아보았다.

힌트

이 문제는 단순히 DFS로만 풀 수 있는 문제가 아닌 DP와 결합해서 풀어야 하는 문제였다.

C	D	Z
E	C	E
A	B	A

만약 위와 같은 문자판에서 ABCD를 찾아야 한다면

가장 먼저 (2,0)에 있는 A를 시작으로 BCD를 찾아갈 것이다.

하지만 위의 코드에서는 (2,2)에 있는 A가 문자열을 찾을 때 다시 똑같은 코스를 가야하기 때문에 시간이 낭비될 것이다.

이를 해결하기 위해 이미 지나간 길은 표시를 해두어 이 길을 지나면 몇가지 경우의 수가 나온다는 것을 저장해두는 방식을 사용하는 것이다.

이 방식을 DP의 메모이제이션 이라고 부른다.

정답 코드

C++

#include <iostream>
#include <string>
#include <cstring>

#define MAXINT 101
using namespace std;

char arr[MAXINT][MAXINT]; //문자판 배열
int dp[MAXINT][MAXINT][MAXINT]; //메모이제이션을 위한 배열
int n, m, k, len, sum = 0, dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
string input; //찾고자 하는 문자열

int find(int idx, int x, int y) { //DFS함수
    if (dp[x][y][idx] != -1) {  //이미 지나갔던 길이라면 저장된 수 리턴
        return dp[x][y][idx];
    }
    if (idx >= len) //문자열을 다 찾았다면 경우의 수 1 추가
        return 1;

    dp[x][y][idx] = 0; //이미 지나갔다는 표시 (0이 유지되면 길이 없으니 그만하라는 표시)

    for (int i = 0; i < 4; i++) { //4방향 탐색
        for (int j = 1; j <= k; j++) { //한 방향을 k만큼 탐색
            int tx = x + dir[i][0] * j; //임시 x 좌표
            int ty = y + dir[i][1] * j; //임시 y 좌표
            if (tx < 1 || tx > n || ty < 1 || ty > m) //x, y 좌표가 문자판을 벗어나면 넘어가기
                continue;
            if (arr[tx][ty] == input[idx]) { //해당 위치의 문자가 찾는 문자와 일치
                dp[x][y][idx] += find(idx + 1, tx, ty); //다음 문자를 찾아 경우의 수 dp배열에 저장
            }
        }
    }
    return dp[x][y][idx]; 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) { //문자판 입력
        for (int j = 1; j <= m; j++)
            cin >> arr[i][j]; 
    }

    memset(dp, -1, sizeof(dp));  //dp 배열 -1로 초기화

    cin >> input;
    len = input.length();
    for (int i = 1; i <= n; i++) { //첫번째 문자 찾아서 dfs함수 돌리기
        for (int j = 1; j <= m; j++) {
            if (arr[i][j] == input[0]) 
                sum += find(1, i, j);
        }
    }
    cout << sum;
}

위 코드에서 dp[x][y][idx]에 x,y를 idx번째로 지나갔을 때 나오는 경로의 수를 저장한다.

이 방법은 공간적인 낭비가 조금 있지만 시간적으로 더 빠른 결과를 가져온다.

유용하게 사용할 것 같다.