[알고리즘 BFS & DFS 9] LETTER

문제

---

세로 R칸, 가로 C칸으로 나누어진 표 모양의 판이 있다. 판의 각각의 모든 칸에는 대문자 알파벳이 하나씩 적혀 있다. 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 인접한 네 칸(상하좌우) 중의 한 칸으로 이동할 수 있다. 이때 매순간 여태 지나온 칸에 적힌 알파벳과 다른 알파벳 칸으로만 이동할 수 있다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

말이 가능한 많은 칸을 지나도록 할 때, 몇 칸을 이동할 수 있는지 구하는 프로그램을 작성하시오. 말이 지나는 칸은 초기에 말이 위치했던 칸도 포함된다.

 

입력

---

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R, C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 C개의 대문자 알파벳들이 주어진다.

 

출력

---

첫째 줄에 말이 이동할 수 있는 칸의 최대값을 출력한다.

 

예제 입력

2 4

JOOS

OBJS

예제 출력

3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

//백준 1987번
 
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<memory.h>
using namespace std;
 
const int MAX = 25;
char arr[MAX][MAX];
//첫번째 말
char horse;
 
int check[MAX][MAX];
char arrCheck[10000];
 
int r,c;
 
//좌표 구조체 생성
typedef struct coor{
  int x;
  int y;
  int cnt;
  coor(){};
  coor(int _x, int _y, int _cnt):x(_x), y(_y), cnt(_cnt){};
}coor;
 
queue <coor> q;
 
//4방면, inside 함수
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
bool inside(int x, int y){
  return (x>=0 && x<r) && (y>=0 && y<c);
}
 
int maximum = 0;
 
void DFS(int x, int y, int cnt){
  if(arr[x][y] == horse && x!=0 && y !=0){
    //이동거리 저장 및 리턴
    if(cnt>maximum) maximum = cnt;
    return;
  }
  
  check[x][y] = 1;
  
  int nx, ny;
  for(int i=0; i<4; i++){
    nx = x + dx[i];
    ny = y + dy[i];
    if(inside(nx,ny) && check[nx][ny]==0 && arrCheck[arr[nx][ny]] == 0){
      check[nx][ny] = 1;
      arrCheck[arr[nx][ny]] = 1;
      DFS(nx, ny, cnt+1);
      check[nx][ny] = 0;
      arrCheck[arr[nx][ny]] = 0;
    }
  }
  
  if(cnt>maximum) maximum = cnt;
}
 
int main(){
  
  scanf("%d %d",&r,&c);
  for(int i=0; i<r; i++){
    for(int j=0; j<c; j++){
      scanf("\n%c",&arr[i][j]);
      if(i==0 & j==0) horse = arr[i][j];
    }
  }
  
  arrCheck[arr[0][0]]=1;
  DFS(0,0,1);
  
  cout<<maximum<<endl;
  
  /*
  for(int i=0; i<r; i++){
    for(int j=0; j<c; j++){
      printf("%d",check[i][j]);
    }
    printf("\n");
  }
  */
  
  
  
  
  return 0;
}