[그래프] 백준 1987 알파벳

참조한 블로그 http://egloos.zum.com/jsh1223/v/9853859

재귀 부분에서 dfs(nx,ny,cnt+1)을 

++cnt로 했는데 틀렸습니다 가 나왔다. 차이는 나중에 생각해 봐야겠다. 

새로 배운 것

1. 플러드 필에서 이동할 때 썼던 int dx,dy 배열을 한번에 2차원 배열로 사용하는 방법

2. 앞에것 을 방문했는지를 확인하는 데에 원래 배열을 만들어서 이전에 방문했던 지점을 

저장하고, for문을 이용해서 그 것을 매번 다음 nx,ny를 방문할 때마다 반복해야 했다. 

하지만 이 코드로 bool ch에 배열 number로 저장해서 한번에 찾을 수 있다는 걸 알았다. 

3. 백트래킹에 대해 아주 많이 생각해 보게 되었다. 

#include <iostream>

using namespace std;

int r, c;

char a[22][22];

bool ch[26];

int dd[][2] = { { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } };

int ans = 0;

void dfs(int x, int y, int cnt) {

       if (cnt > ans) ans = cnt;

       for (int k = 0; k < 4; ++k) {

               int nx = x + dd[k][0];

               int ny = y + dd[k][1];

               if (0 <= nx&&nx < r && 0 <= ny&&ny < c) {

                      if (ch[a[nx][ny] - 'A'] == false) {

                              ch[a[nx][ny] - 'A'] = true;

                              dfs(nx, ny, cnt+1);

                              ch[a[nx][ny] - 'A'] = false;

                      }

               }

       }

}

int main() {

       cin >> r >> c;

       for (int i = 0; i < r; ++i) {

               cin >> a[i];

       }

       ch[a[0][0] - 'A'] = true;

       dfs(0, 0, 1);

       cout << ans;

       return 0;

       

}