[그래프 / BOJ 1987 / C++] 알파벳

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

1987번: 알파벳

1) 
1-1) 만약 채워졌다면, 그 숫자를 확인한 후 개수를 세준다.
1-2) 만약 안채워졌다면, 사각형을 9등분한 후 각 사각형마다 다시 1) 과정을 반복한다. 

 

이 문제도 역시 아래 문제를 풀고오면 이해가 더 쉬워진다!!

https://die-will-coding.tistory.com/38#comment14785555

[그래프 / BOJ 1325 / C++] 효율적인 해킹

 

백트래킹으로 모든 경우의 수를 탐색하면 깔끔하게 해결할 수 있다.

 

그림을 그리면 이해가 빠르다!

이 예시를 'C' (1,1)에서 시작하여 모든 경우의 수를 탐색하는 방법을 보자.

 

(사실 LEVEL2의 A를 택하면 C라는 선택지가 생기는데, 이는 지금은 무시한다고 생각하자.)

 

최대로 말이 갈 수 있는 칸 수를 찾으면 되니깐, LEVEL의 최댓값을 구하면 끝나는 문제다!!

 

기존 2차원배열에서의 dfs 형식에 중복되는 알파뱃은 제거한다는 로직을 넣어주면 간단하게 해결된다.

 

이 문제 역시 dfs의 return 값은 int로 넘긴다는 사실을 잊지말자!!

 

이 return의 int 값은 level이다!!

 

 

 

#include <bits/stdc++.h>

using namespace std;

int R, C, res;
int bd[25][25];
int useAlph[26];


int dy[4] = {0, -1, 0, 1};
int dx[4] = {1, 0, -1, 0};

int dfs(int y, int x, int level){
    
    useAlph[bd[y][x]] = 1; // 해당 알파뱃 사용 체크.
    
    int ret = level;
    
    for(int i = 0 ; i < 4 ; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        
        if(ny > R || nx > C || ny <= 0 || nx <= 0) continue;
        if(useAlph[bd[ny][nx]]) continue; // 해당 알파벳이 사용됐다면 무시.
        
        ret = max(ret, dfs(ny, nx, level+1));
        
        useAlph[bd[ny][nx]] = 0; // 원래대로 돌려주기
        
    }
    
    
    
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> R >> C;
    
    
    for(int i = 1 ; i <= R ; i++){ // (1.1) 부터 시작.
        string s="";
        cin >> s;
        
        for(int j = 0 ; j < C ; j++){
            bd[i][j+1] = (s[j]-'A'); // 0~26으로 알파뱃 표현.
        }
    }
    
    res = dfs(1,1,1);
    
    cout << res;
    
}