[백준] 1987 알파벳 (C++)

문제 URL

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

1987번: 알파벳

[문제 설명]

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

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

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하라.

 

 

 

[문제 풀이]

백트래킹을 구현하여 풀 수 있는 문제이다. 말의 현재 위치를 true로 두고 DFS를 진행해 준 뒤, 이동할 수 없을 때까지 반복하여 빠져나오면 말의 현재 위치를 다시 false로 바꾸어 준다. 이때, cnt 변수를 통해 몇 번 이동했는지 세어준다.

---

#include<iostream>
#include<queue>
using namespace std;
 
int R, C, Answer;
char MAP[20][20];
bool Visit[26];

// 오른, 왼, 아래, 위
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
int Bigger(int A, int B) { 
    if (A > B) 
        return A; 
    return B; 
}

void DFS(int x, int y, int Cnt) {
    Answer = Bigger(Answer, Cnt);
    
    for (int i = 0; i < 4; i++) {
        // 상하좌우로 이동
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (nx >= 0 && ny >= 0 && nx < R && ny < C) {
            if (Visit[MAP[nx][ny] - 'A'] == false) {
                Visit[MAP[nx][ny] - 'A'] = true;
                DFS(nx, ny, Cnt + 1);
                Visit[MAP[nx][ny] - 'A'] = false;
            }
        }
    }
}

int main(void) {
    cin >> R >> C;
    
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> MAP[i][j];
        }
    }
    
    Visit[MAP[0][0] - 'A'] = true;
    DFS(0, 0, 1);
 
    cout << Answer << '\n';
}

참고: https://yabmoons.tistory.com/84