알파벳

알고리즘 구분 : 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 백트래킹

문제

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

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

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

입력
첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력
첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

예제 입력 1
2 4
CAAB
ADCB
예제 출력 1
3
예제 입력 2
3 6
HFDFFB
AJHGDH
DGAGEH
예제 출력 2
6
예제 입력 3
5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH
예제 출력 3
10

문제 풀이

문제를 다 읽자마자 이 문제는 백트래킹 유형이라고 판단했다. 판단의 이유는 최대로 갈 수 있는 거리를 찾아야 하는데, 이는 특정 위치까지 DFS와 같은 방식으로 접근하였다가, 더 이상 움직일 수 없을 때 빠져나와 새로운 길을 들어가서 더 큰 결과를 가져올 수 있는지 확인하는 과정이 필요한데, 이 것이 백트래킹의 전형적인 알고리즘이기 때문이다.

1) 시작 위치에서 시작 위치를 방문 처리한 이후 해당 위치에서 방문이 가능한 위치를 찾는다.

2) 방문이 가능한 위치로 이동한다.

3) 방문이 가능한 위치에서 다시 방문이 가능한 위치를 찾는다.

4) 만약 방문이 가능한 위치가 없다면 현재까지 cnt를 return한다.

위의 과정을 그대로 구현하였다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

int r, c;
bool already[27]; // 이미 방문한 집합
int graph[21][21];
int backTracking(int x, int y, int cnt);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    memset(graph, 0, sizeof(graph));
    memset(already, 0, sizeof(already));

    cin >> r >> c;
    for(int i = 1; i < r + 1; i++) {
        for(int j = 1; j < c + 1; j++) {
            char input;
            cin >> input;
            graph[i][j] = input - 'A';
        }
    }

    cout << backTracking(1, 1, 1) << endl;

    return 0;
}

int backTracking(int x, int y, int cnt) {
    int maxCnt = cnt;
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};

    already[graph[x][y]] = true;
 
    
    for(int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(nx < 1 || nx > r || ny < 1 || ny > c) {
            continue;
        }

        if(already[graph[nx][ny]] == false) {
            maxCnt = max(maxCnt, backTracking(nx, ny, cnt + 1));
        }
    }

    already[graph[x][y]] = false;

    return maxCnt;
}

• 문제 출처 : https://www.acmicpc.net/problem/1987
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.