백준 1987

문제

세로 𝑅칸, 가로 𝐶칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

풀이

전형적인 백트래킹문제이다.

(0,0) 부터 시작해서 중복되지 않는 알파벳이 나올 경우 한칸씩 갈 수 있는 문제로 재귀의 깊이에 따른 시간복잡도를 주의해야되는 문제이다.

정확한 증명은 못하겠지만, 알파벳의 개수는 총 26개이므로 최대 26칸을 방문할 수 있다. 그리고 각 칸을 한번씩만 방문할 수 있으므로 O(R * C)로 생각하고 구현했다.

 

 

 

코드

#include <iostream>
#include <string>
using namespace std;

int R, C, dx[4]={0,1,0,-1}, dy[4]={1,0,-1,0}, ans=0;
string board[21];

void func(int i, int j, int a, int* alpha) {
    for(int dir=0; dir<4; dir++) {
        int nx = i + dx[dir];
        int ny = j + dy[dir];
        if(nx<0||nx>=R||ny<0||ny>=C) continue;
        if(alpha[board[nx][ny]-'A']) continue;
        alpha[board[nx][ny]-'A'] = 1;
        func(nx, ny, a+1, alpha);
        alpha[board[nx][ny]-'A'] = 0;
    }
    ans = max(ans, a);
}

int main() {
    cin>>R>>C;
    for(int i=0; i<R; i++)
        cin>>board[i];
    int alpha[26] = {0};
    alpha[board[0][0] - 'A'] = 1;
    func(0,0,1,alpha);
    cout<<ans;
}