[DFS, 백트래킹] BOJ 1987 알파벳 (C++) + 내가 썼던 반례

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

1987번: 알파벳

 

문제 해결 알고리즘

 

백트래킹, 깊이 우선 탐색 문제

 

(0, 0)부터 DFS를 해주는데 이 때, 문제에서 나온 것처럼 중복되는 알파벳을 체크해주는 배열과, 지나온 자리들을 체크해주는 배열을 각각 두고 탐색하는데 시간을 아낀다. 나머지는 그냥 전형적인 백트래킹이다.

 

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

int R, C; 
char arr[21][21];
bool visited[21][21];
int dir[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
vector<bool> vec(26);
int result = 0;

bool isIn(int x, int y){
    return 0<=x && x<R && 0<=y && y<C;
}

void dfs(int x, int y, int cnt){

    result = max(cnt, result);

    for(int i=0;i<4;i++){

        int next_x = x + dir[i][0];
        int next_y = y + dir[i][1];
        
        //배열 범위 안에 있어야하고, 한 번도 지나지 않은 알파벳인지
        if(isIn(next_x, next_y) && !vec[arr[next_x][next_y] - 'A'] && !visited[next_x][next_y]){
            
            vec[arr[next_x][next_y] - 'A'] = true;
            visited[next_x][next_y] = true;

            dfs(next_x, next_y, cnt+1);

            vec[arr[next_x][next_y] - 'A'] = false;
            visited[next_x][next_y] = false;
        }
    }
}

int main(){
    cin >> R >> C;

    // 알파벳 배열 입력
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            cin >> arr[i][j];
        }
    }

    //시작 지점 알파벳 체크, 시작 지점 체크
    vec[arr[0][0] - 'A'] = true;
    visited[0][0] = true;

    dfs(0, 0, 1);

    cout << result;

}

 

내가 쓴 반례

 

2 5 

A J I H G 
B C D E F

result = 10

2 5

A A I H G
B C D E F

result = 9

2 2

A A
A A

result = 1

1 1

A

result = 1