[백준 - 1987] 알파벳 (DFS)

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

1987번: 알파벳

문제에서 요구하는 것은 (0,0) 인덱스에서 시작해서 한 칸씩 상하좌우로 이동할 때,

 

중복된 알파벳을 피해서 최대한 이동 가능한 횟수를 찾는 것입니다.

이전에 했던 토마토처럼 탐색형 문제이면서 DFS를 이용하는 문제입니다.

 

( BFS도 가능할 겁니다.)

---

알파벳 문제는 경로 탐색형 문제입니다. 해결 방법은 크게 DFS, BFS 두 가지가 있습니다.

 

확인해줘야 하는 것은 알파벳의 중복성, 이미 확인한 경로인가?입니다.

 

그리고 이전 값으로 돌아올 경우 이전에 지난 데이터는 원상 복구시켜줘야 합니다.

---

문제를 보자마자 DFS로 풀이를 잡았습니다. 

 

신경 써줘야 하는 조건은 다음과 같습니다.

< 조건 >

1. 이미 지난 알파벳인가? -> bool array로 26개 만들고 처리해줍시다.

2. 방문한 곳인가? -> B, DFS에서 기본인 bool visit array로 처리합니다.

1. 처음에는 간단하게 생각해서 단순 DFS로 풀려고 했습니다.

 

하지만 문제가 발생한 것은 이미 지나온 경로와 데이터를 처리할 수 없었습니다.

 

예를 들어, 하나의 경로에서 뻗어나가는 4가지 경우의 수(상, 하, 좌, 우) 중에 2번째(하 이동)에 들어간 DFS가 끝났다고 해서 그 값이 최대라는 보장이 없습니다.

 

이후 3번째(좌 이동), 4번째(우 이동) DFS에서 더 많은 이동이 나올 수도 있기 때문입니다.

---

2. 그래서 중복을 없애면서 모든 경우를 다 확인하는 형식의 DFS를 진행해야겠다고 생각을 했습니다.

 

이와 같은 연습하기 가장 좋은 게 N과 M 시리즈입니다.

 

DFS를 빠져나온 뒤 진행되는 코드에 해당 인덱스의 알파벳과 방문을 false로 바꿔주고, 경로를 -1 해주는 것입니다.

 

즉, 내가 처리한 경로를 없던 셈 치고 진행을 하겠다는 겁니다.

 

그 후 그냥 if문 조건이 넘어가면 max값 비교를 하게 짰더니 문제가 발생하더군요.

 

그냥 조건이 안 맞으면 무조건 max값을 처리해 버리지 뭡니까...

---

3. 해결 방법은 단순했습니다. 상하좌우 어디로도 이동이 불가능하면 그때 max를 처리해주면 됩니다.

 

즉 이동 반복문의 iterator가 최댓값 3에 도달한 경우, max 비교를 해주면 됩니다.

---

#include <iostream>
#include <cstdlib>
#include <cmath>
#include <string>
using namespace std;

int dirx[4] = {-1, 0, 0, 1};
int diry[4] = {0, -1, 1, 0};
int R, C;
int cnt;
int result = -1;
char map[20][20];
bool visit[20][20];
bool alphabet[26]; // A = 0 ~ Z = 25

void dfs(int x, int y) {
    visit[x][y] = true;
    cnt++;
    
    for (int i = 0; i < 4; i++) {
        int nx = x + dirx[i];
        int ny = y + diry[i];
        
        if (nx >= 0 && nx < R && ny >= 0 && ny < C) {
            if (!visit[nx][ny]) {
                char next_alphabet = map[nx][ny];
                
                if (!alphabet[next_alphabet - 'A']) {
                    alphabet[next_alphabet - 'A'] = true;
                    dfs(nx, ny);
                    alphabet[next_alphabet - 'A'] = false;
                    visit[nx][ny] = false;
                    cnt--;
                }
            }
        }
        
        if (i == 3)
            result = max(cnt, result);
    }
}


int main() {
    string input;
    
    cin >> R >> C;
    
    for (int i = 0; i < R; i++) {
        cin >> input;
        for (int j = 0; j < C; j++) {
            map[i][j] = input[j];
        }
    }
    
    alphabet[map[0][0] - 'A'] = true;
    dfs(0, 0);
    
    cout << result << "\n";
    
}

좀 깔끔하게 풀은 거 같네요.

 

삼성 A형을 따기 위해서 요즘 B, DFS 위주의 공부를 하는 중인데 익숙지가 않습니다...;; 

 

 

깃허브 - https://github.com/cow-coding/algorithm/blob/master/BOJ/1987.cpp