[백준/Baekjoon] 1987 알파벳 C++ :: DFS

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

1987번: 알파벳

---

1. Logic

- 문자 하나를 지날 때 마다 체크를 해서 다음 경로에서 이전에 어떤 문자를 지나왔는지를 확인해야하기 때문에 처음에는 자료구조 중 map을 사용해서 체크했다.

 

경로를 체크한 후 방문 처리한 계속 남아있게 되면 다른 경로를 진입할 때 continue 처리가 되기 때문에  DFS를 빠져나오면서 map에서 키값을 false로 돌려놔준다.

 

방문처리 하는 법

1. 자료구조 Map을 활용

2. 배열을 활용한 방법

  - (대문자 - 'A') 숫자로 나오기 때문에 해당 배열에 값을 true / false로 변환하며 체크

 

맵을 활용하게 되면 시간복잡도가 1600언저리 나오지만 배열을 활용하게 되면 시간복잡도가 확 줄어든다.

Map에 넣다 뺐다 하는 과정에서 해시로 변환을 해야하기때문에 걸리는 것 같지만 확실하지 않다.

---

2. Code

자료구조 Map을 사용한 방법

#include<bits/stdc++.h>

using namespace std;

int n, r;
int ans = 0;

vector<string> vec;
map<char, bool> m;

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

int solve(int x, int y) {
    int ret = 1;
    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 >= n) continue;
        if(m[vec[ny][nx]]) continue;
        m[vec[ny][nx]] = true;
        ret = max(ret, solve(nx, ny) + 1);
        m[vec[ny][nx]] = false;
    }

    return ret;
}

int main() {
    cin >> n >> r;

    for(int i = 0; i < n; i++) {
        string str;
        cin >> str;
        vec.push_back(str);
    }

    m[vec[0][0]] = true;
    
    cout << solve(0, 0);
}

 

배열을 활용한 방법

#include<bits/stdc++.h>

using namespace std;

int n, r;
int ans = 0;

vector<string> vec;
bool vis[26];

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

int solve(int x, int y) {
    int ret = 1;
    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 >= n) continue;
        if(vis[vec[ny][nx] - 'A']) continue;
        vis[vec[ny][nx] - 'A'] = true;
        ret = max(ret, solve(nx, ny) + 1);
        vis[vec[ny][nx] - 'A'] = false;
    }

    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> r;

    for(int i = 0; i < n; i++) {
        string str;
        cin >> str;
        vec.push_back(str);
    }

    vis[vec[0][0] - 'A'] = true;
    
    cout << solve(0, 0);
}

 

---

 

 

3. Feedback

BFS를 많이 사용해서 익숙해서 BFS로 처음에는 풀이하려고 했지만 알파벳 중복처리를 하는 과정에서 문제가 생겼다. BFS는 병렬로 움직이기 때문에 만약 이전의 경로에서 다른 알파벳 2개가 나오면 이후의 과정에서 걸러지기 때문에 DFS로 변경하여 깊이 들어가며 중복체크를 하고 루프에서 나오면서 방문을 풀어주어 다음 경로에서 걸리지 않게 해주었다.

 

DFS를 사용하여 풀면 좋은 문제와 BFS를 사용하여 풀면 좋은 문제가 뭔지 이해한듯?

 

중복처리를 해주는 방법 또한 처음에 map을 사용했을 때에는 시간복잡도가 엄청 오래걸렸지만 배열을 사용해보니 시간복잡도가 거의 1/4꼴로 줄었다. 상황에 맞는 적절한 컨테이너를 사용하는 것 또한 엄청 중요하다는 것을 깨달았다. 

 

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐