재귀 부분에서 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;
}
'알고리즘' 카테고리의 다른 글
[DP] 백준 동전 2 2294 (0) | 2018.04.02 |
---|---|
[DP] 백준 2011 암호코드 (0) | 2018.01.02 |
[그래프] 백준 5567 결혼식 (0) | 2017.12.13 |
[EAZY] 백준 1065번 한수 (0) | 2017.08.17 |
[EAZY] 백준 4673 셀프넘버 (0) | 2017.08.15 |