[백준][오류 해결] bus error 1987번 : 알파벳 - C/C++

백준 1987번 알파벳 문제를 해결하면서 발생한 문제에 대해 이야기해보려한다.

728x90

우선 내가 제출한 코드는 아래와 같다.

#include <iostream>
#include <string>
#include <algorithm>

//알파벳
using namespace std;

int r, c;
int cnt;
int alpabet_cnt[26] = {0};
char map[20][20];

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

void dfs(int y, int x, int cnt2){
    for(int i = 0; i < 4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];

        if(ny < 0 || ny >= r || nx < 0 || nx >= c){
            continue;
        }

        char next_char = map[ny][nx];
        if (next_char < 'A' || next_char > 'Z') continue;

        if(alpabet_cnt[next_char - 'A'] == 1){
            continue;
        }

        alpabet_cnt[next_char - 'A'] = 1;
        cnt = max(cnt, cnt2 + 1);
        dfs(ny, nx, cnt2 + 1);
        alpabet_cnt[next_char - 'A'] = 0;
    }
}

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

    for(int i = 0; i < r; i++){
        string input_map;
        cin >> input_map;
        for(int j = 0; j < c; j++){
            map[i][j] = input_map[j];
        }
    }

    alpabet_cnt[map[0][0] - 'A'] = 1;
    dfs(0, 0, 1);

    cout << cnt << '\n';

    return 0;
}

 

DFS와 백트래킹으로 푸는 문제인데 왜 틀렸을까.

분명 vscode로 돌렸을 때는 맞다고 뜨는데

사실 bus error가 많이 발생했다.

 

bus error가 발생하는 이유/원인은 아래와 같다.

'모든 경로를 탐색하지 못하고 cnt를 전역변수로 관리'하였기 때문이다.

 

이 부분의 코드를 고쳐보자.

 

cnt는 필자가 설정한 것처럼 전역변수로 유지해도 되지만,

dfs가 종료될 때마다 갱신해주어야한다. (이 부분을 놓친 듯)

 

그렇다면 언제 갱신해야 하는가.

cnt2 값을 받아 더 이상 이동할 수 없을 때에 갱신해야 한다.

 

더이상의 이동이 불가하다면 max(cnt, cnt2) 를 수행하자.

 

 

수정한 코드는 아래와 같다.

#include <iostream>
#include <string>
#include <algorithm>

//알파벳
using namespace std;

int r, c;
int cnt;
int alpabet_cnt[26] = {0};
char map[20][20];

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

void dfs(int y, int x, int cnt2) {
    cnt = max(cnt, cnt2);  // 현재 경로 길이로 최대값 갱신

    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if (ny < 0 || ny >= r || nx < 0 || nx >= c) {
            continue;
        }

        int index = map[ny][nx] - 'A';
        if (alpabet_cnt[index] == 0) {
            alpabet_cnt[index] = 1;
            dfs(ny, nx, cnt2 + 1);
            alpabet_cnt[index] = 0;
        }
    }
}

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

    for (int i = 0; i < r; i++) {
        string input_map;
        cin >> input_map;
        for (int j = 0; j < c; j++) {
            map[i][j] = input_map[j];
        }
    }

    alpabet_cnt[map[0][0] - 'A'] = 1;
    dfs(0, 0, 1);

    cout << cnt << '\n';

    return 0;
}

 

 

처참한 결과다.

어렵긴 정말 어려운 것 같다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

더 좋은 풀이가 있다면 댓글로 알려주세요 !!

피드백 환영입니다☺️