[백준/C++] 1987번 알파벳

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

1987번: 알파벳

맨날 다익스트라나 bfs만 연습하다가 오랜만에 풀어본 dfs문제이다.

dfs를 익히기에 아주 좋은 문제라고 생각되어 포스팅해본다! 크게 어렵지도 않아서 dfs에 능숙하지 않은 나같은 사람도 잘(?) 풀 수 있으리라 생각한다.

풀이

1. 우선, R x C 모양의 보드를 입력받아준다.

2. 그리고 0,0 위치(=시작 위치)도 말이 갈 수 있는 칸 중 하나로 친다고 하였으므로 해당 위치의 알파벳의 방문 횟수를 1 증가시켜주고, 시작 위치 0,0과 depth를 1로 하여 dfs를 실행한다.

3. 말이 갈 수 있는 최대 칸 수를 구하는 것이므로 max함수를 이용한 최댓값 계산 코드를 적어준다.

4. dfs를 실행하는데, 우선 현재 위치의 알파벳이 방문하지 않은 알파벳이라면 방문 횟수를 1 증가시켜주고 현재 위치와 depth에 +1 한 값을 이용하여 dfs를 재귀적으로 실행한다.

※ dfs는 깊이 우선 탐색이므로 특정 노드에 대해 끝까지 파고들어간다.​

5. 특정 노드에 대해 깊이 우선 탐색이 끝나면, 다른 경로에 대해 탐색도 필요하므로 방문 횟수를 1 감소시켜준다! -> 백트래킹하기 위한 코드

6. 인접한 나머지 노드들에 대해서도 dfs를 실행한다!

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

int r,c,ans;
string str;
char map[21][21];

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

void dfs(int x,int y,int depth) {
    ans = max(depth, ans);
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
            if (!alpha[map[nx][ny]-65]){
                // 현재 위치의 알파벳을 방문한 알파벳으로 저장
                alpha[map[nx][ny]-65]++;

                // 해당 정보들을 가지고 dfs 탐색 시작
                dfs(nx, ny, depth+1);

                // 상단의 재귀함수가 끝났다면, 인접한 다른 경로도 확인해야하므로
                // 현재 위치의 알파벳을 방문하지 않은 알파벳으로 변경
                alpha[map[nx][ny]-65]--;
            }
        }
    }
}

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

    cin >> r >> c;

    for(int i=0; i<r;i++){
        cin >> str;
        for(int j=0; j<str.size();j++){
            map[i][j] = str[j];
        }
    }
    alpha[map[0][0]-65]++;
    dfs(0,0,1);

    cout << ans;

    return 0;
}