#1987 알파벳

 

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

1987번: 알파벳

골드 4의 문제이다. 처음 봤을때 이런문제가 왜 골드 4이지? 생각을 했었다. 코드도 쭉쭉 잘 써내려가서 테스트케이스까지 잘 통과하였다. 근데 제출하니까 2%에서 틀렸다고 나왔다. 보자마자 문제가 있음을 인지하고 직접 손으로 써보면서 dfs를 따라가보니까 문제에서 원하는 방향과는 다르게 답이 나오고있었다.

내가 쓰지않은 알고리즘이 있었던것이다. 바로 백트래킹 이다.

 

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int r,c,ans;
char board[21][21];
int check[26];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

void dfs(int x,int y,int cnt){
  if(cnt>ans)
    ans=cnt;
  check[board[x][y]-'A']=1;
  for(int k=0;k<4;k++){
    int nx=x+dx[k];
    int ny=y+dy[k];
    if(0<=nx&&nx<r && 0<=ny && ny<c){
      if(check[board[nx][ny]-'A']==0){
        check[board[nx][ny]-'A']=1;
        dfs(nx,ny,cnt+1);
        check[board[nx][ny]-'A']=0;
      }
    }
  }
}

int main()
{
  freopen("input.txt","r",stdin);
  cin>>r>>c;
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      cin>>board[i][j];
    }
  }
  dfs(0,0,1);
  
  cout<<ans;
}

처음에는 백트래킹 따위는 고려하지않고 어떤 정점에서 4방향을 따져본다음 나오지않았던 알파벳이라면 탐색하는 방식으로 진행했었다. 그렇게 하면 이상한 방법으로 탐색을 진행 할 수도 있다. 예를들어 문제의 2번째 테케에서, 답은 

H->F->J->A->D->G 로 6인데, 내 코드에서는 H->F->D->(되돌아가서) J->G->A 로 6이 나왔다.

이 부분에서 백트래킹이 필요했던 것이다. 특정 정점으로 들어갔을때 답이 나오지않을것 같다 싶으면 다시 돌아와서 다른 방향으로 탐색을 진행해야한다. 

 

그래서 dfs를 구현할때 x,y좌표 뿐만아니라 cnt를 선언하여 답을 구할 수 있게 하였다.

핵심 코드는 다음과 같다.

for(int k=0;k<4;k++){
    int nx=x+dx[k];
    int ny=y+dy[k];
    if(0<=nx&&nx<r && 0<=ny && ny<c){
      if(check[board[nx][ny]-'A']==0){
        check[board[nx][ny]-'A']=1;
        dfs(nx,ny,cnt+1);
        check[board[nx][ny]-'A']=0;
      }
    }
  }

여기서 check배열에 특정 알파벳이 등장했다면 1을 넣어주고, check배열이 0이라면 등장한적 없던 알파벳인 것이다.

if(check[board[nx][ny]-'A']==0){
    check[board[nx][ny]-'A']=1;
    dfs(nx,ny,cnt+1);
    check[board[nx][ny]-'A']=0;

}

이 부분에서  check[board[nx][ny]-'A']=0; 이 코드가 핵심이다. 왜냐면 나온적 없는 알파벳이라면 check에서 0 일테니까 if문을 충족하여  check[board[nx][ny]-'A']=1; 이 부분을 실행하여 나왔다고 기록한다. 그리고 dfs를 재귀적으로 호출해 그 주변의 정점을 탐색하고 돌아온다. 그리고 다시 0을 대입해 쓴적 없다고 기록하는것이다. 왜냐면 앞으로 다시 나왔을때 방문해야할 수도 있기 때문!

 

문제가 쉬워 보여서 골드4여도 쉬운가보다 했는데 역시 아니었다 ㅎㅎ;;; 백트래킹 문제를 더 연습해야겠다.