백준 1987 알파벳 - dfs와 백트래킹 (c++)

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

1987번: 알파벳

 

dfs + 백트래킹 문제였다.

알파벳 별로 방문을 한번이라도 했는지 안했는지를 alphavisited로 마킹하면서 확인.

하지만 백트래킹하는 과정에서 내가 실수를 한건지 alphavisited부분이 제대로 마킹이 안됐었다.

아래쪽에 있는게 실패한 코드.

#include <iostream>
#include <queue>
using namespace std;
 
int R,C;
int result=-1;
char map[20][20];
bool alphavisited[26];
 
typedef struct{
    int y,x;
}Dir;
Dir movedir[4] = {{1,0},{-1,0},{0,1},{0,-1}};
 
void dfs(int y, int x, int count){
 
    int alphavIndex = map[y][x]-'A';
    cout<<alphavIndex<<"\n";
    if(alphavisited[alphavIndex]){ //1차로 코딩한 직후 디버깅해보니 이부분이 아예 안돌아 간다.
        result = max(result,count);
        return;
    }
    alphavisited[alphavIndex]= true;
    for(int i=0; i<4; i++){
        int ny = y+movedir[i].y;
        int nx = x+movedir[i].x;
        if(nx>=0 && nx<C && ny>=0 && ny<R){
            if(!alphavisited[map[ny][nx]-'A']){
 
                dfs(ny,nx,count+1);
            }
        }
    }
    alphavisited[alphavIndex]= false; //이거 필요?
 
}
 
int main(void){
    cin>>R>>C;
    for(int i=0; i<R; i++){
        cin>>map[i];
    }
    dfs(0,0,1);
    cout<<result;
}

 

그 다음으로 수정해서 내본 코드.

이 아래에 있는게 ac받은 코드인데, 내가 봤을땐 분명히 정답인데 오답이 떠서 그 이유를 찾아봤더니,,

map[20][20]으로해서 틀렸다고 질문게시판에 써져있는걸 봤다;;;

 

교훈

- 방문노드 마킹에 조심하자.

 - string으로 입력 받을때는 하나 여유롭게 배열의 사이즈를 받자..

#include <iostream>
#include <queue>
using namespace std;
 
int R,C;
int result=-1;
char map[21][21];
bool alphavisited[26];
 
typedef struct{
    int y,x;
}Dir;
Dir movedir[4] = {{1,0},{-1,0},{0,1},{0,-1}};
 
void dfs(int y, int x, int count){
 
    int alphavIndex = map[y][x]-'A';
    alphavisited[alphavIndex]= true;
    for(int i=0; i<4; i++){
        int ny = y+movedir[i].y;
        int nx = x+movedir[i].x;
        if(nx>=0 && nx<C && ny>=0 && ny<R){
            if(alphavisited[map[ny][nx]-'A']){
                result = max(result,count);
            }
            else if(!alphavisited[map[ny][nx]-'A']){
 
                dfs(ny,nx,count+1);
                alphavisited[map[ny][nx]-'A']=false;
            }
        }
    }
 
 
}
 
int main(void){
    cin>>R>>C;
    for(int i=0; i<R; i++){
        cin>>map[i];
    }
    dfs(0,0,1);
    cout<<result;
}