백준 2186 - 문자판

문제 설명

알파벳 대문자가 한 칸에 한 개씩 적혀있는 N×M 크기의 문자판이 있다. 편의상 모든 문자는 대문자라 생각하자. 예를 들어 아래와 같은 문자판을 보자.

이 문자판의 한 칸(아무 칸이나 상관없음)에서 시작하여 움직이면서, 그 칸에 적혀 있는 문자들을 차례대로 모으면 하나의 단어를 만들 수 있다. 움직일 때는 상하좌우로 K개의 칸까지만 이동할 수 있다. 예를 들어 K=2일 때 아래의 그림의 가운데에서는 'X' 표시된 곳으로 이동할 수 있다.

반드시 한 칸 이상 이동을 해야 하고, 같은 자리에 머물러 있을 수 없다. 또, 같은 칸을 여러 번 방문할 수 있다.

이와 같은 문자판과 K, 그리고 하나의 영단어가 주어졌을 때, 이와 같은 영단어를 만들 수 있는 경로가 총 몇 개 존재하는지 알아내는 프로그램을 작성하시오.

위의 예에서 영단어가 BREAK인 경우에는 다음과 같이 3개의 경로가 존재한다. 앞의 수는 행 번호, 뒤의 수는 열 번호를 나타낸다.

• (4, 2) (3, 2) (2, 2) (1, 2) (1, 1)
• (4, 2) (3, 2) (2, 2) (1, 2) (1, 3)
• (4, 2) (3, 2) (2, 2) (2, 3) (1, 3)

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 임의의 칸에서 시작하여 주어진 문자열을 완성할 수 있는 경로의 개수를 구하는 것이다.

이때, 한 번에 k칸까지 이동할 수 있다.

 

처음에는 BFS를 통해 완성가능한 경로를 탐색하였지만 시간초과가 발생하였다.

시간을 줄이기 위해 DP를 이용해야 했다.

 

DP를 통해 해당 칸에 depth번째 도착하였을 때 완성할 수 있는 경로의 개수를 기록하는 것이다.

예시에 주어진 상황에서는 B가 하나밖에 없어 위와 같은 경로가 유일하다.

B는 depth가 0인 상태이며, R에 도달하기 위해서는 depth가 1이어야 한다.

이런 식으로 따라가 단어의 마지막에 도달하는 순간 1을 반환한다.

이후, 반환된 값을 현재 DP에 더한다.

 

해당 문제에서는 기본값을 설정하는 부분이 중요하다.

DP의 기본값을 0으로 설정하게 되면 시작점의 DP값이 0이기 때문에 시작점으로 다시 돌아오는 경로가 생긴다.

물론 word의 길이가 작다면 문제가 되지 않겠지만 80글자가 된다고 하면 $80*79....*1$번의 연산을 더 하게 되는 것이다.

따라서, 아예 갈 수 없는 부분과 방문 가능한 부분을 구분할 수 있어야 한다.

따라서, DP를 -1로 초기화하여 사용해야 한다.

 

int DFS(vector<vector<char>>& Board, int y, int x, int depth)
{
    if (DP[y][x][depth] != -1) return DP[y][x][depth];
    if (depth == (int)word.size()-1) return 1;

    DP[y][x][depth] = 0;
    for (int i = 0; i < 4; i++)
    {
        int newY = y;
        int newX = x;

        for (int k = 0; k < K; k++)
        {
            newY += dy[i];
            newX += dx[i];

            if (newY < 0 || newY >= N || newX < 0 || newX >= M) break;
            if (Board[newY][newX] != word[depth+1]) continue;

            DP[y][x][depth] += DFS(Board, newY, newX, depth + 1);
        }
    }

    return DP[y][x][depth];
}

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>

using namespace std;

int N, M, K;
const int MAX = 100;
string word;

vector<int> dy = { -1, 0, 1, 0 };
vector<int> dx = { 0, 1, 0, -1 };
int DP[MAX][MAX][80];

int DFS(vector<vector<char>>& Board, int y, int x, int depth)
{
    if (DP[y][x][depth] != -1) return DP[y][x][depth];
    if (depth == (int)word.size()-1) return 1;

    DP[y][x][depth] = 0;
    for (int i = 0; i < 4; i++)
    {
        int newY = y;
        int newX = x;

        for (int k = 0; k < K; k++)
        {
            newY += dy[i];
            newX += dx[i];

            if (newY < 0 || newY >= N || newX < 0 || newX >= M) break;
            if (Board[newY][newX] != word[depth+1]) continue;

            DP[y][x][depth] += DFS(Board, newY, newX, depth + 1);
        }
    }

    return DP[y][x][depth];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M >> K;

    vector<vector<char>> Board(N, vector<char>(M));
    int ans = 0;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> Board[i][j];
        }
    }

    cin >> word;

    memset(DP, -1, sizeof(DP));

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (Board[i][j] != word[0]) continue;

            ans += DFS(Board, i, j, 0);
        }
    }

    cout << ans;

    return 0;
}

---

 

 

 

 

 

Tip

• c++의 memset은 cstring 헤더에 있다.
  • IDE에서는 문제없이 동작하지만, 백준에서는 안된다.
• 다차원 배열을 매개변수로 넘기는 것은 포인터를 넘기는 것이기 때문에 Call-by-reference이다.
  • vector는 Call-by-Value
• 다차원 배열혹은 큰 크기의 배열을 main함수 안에 선언하면 스택을 잡아먹어 경고가 들어온다.
  • 어차피 전역 변수로 사용해야 한다.
  • vector<vector<vector....이런 방식이 싫어서 다차원 배열을 이용해 봤다.
    • 이차원까지는 괜찮은데 삼차원부터는 가독성이 떨어지는 것 같다.

---