https://www.acmicpc.net/problem/1987
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | #include <iostream> using namespace std; char map[22][22]; int en[26]; int dir[4][2] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } }; int R, C; int ans = 0; void dfs(int nowR, int nowC, int step) { if (step > ans) ans = step; for (int i = 0; i < 4; i++) { int nR = nowR + dir[i][0]; int nC = nowC + dir[i][1]; if (nR < 0 || nC < 0 || nR >= R || nC >= C) continue; if (en[map[nR][nC] - 'A'] == 1) continue; en[map[nR][nC] - 'A'] = 1; dfs(nR, nC, step+1); en[map[nR][nC] - 'A'] = 0; } } int main() { cin >> R >> C; for (int i = 0; i < R; i++) { cin >> map[i]; } en[map[0][0] - 'A'] = 1; dfs(0, 0, 1); cout << ans << '\n'; return 0; } | cs |
최단경로를 구하는 문제처럼 접근하면 안된다.
최단경로를 구하는 것과 달리 목적지가 없어 여러가지 방법으로 순회해도 된다.
if(res[nR][nC] > step+1) 처럼
다음에 갈 곳의 수가 훨씬 크다면 가지 않는데, 당장은 다음에 갈곳이 작더라도
순회했을 때 더 멀리 갈 수 있다.
ABCD
EFAD
ASDA
NGHZ 일 경우
12
3
45
876 의 길이 있음에도 불구하고
12
3
47
656 으로 되기 때문에 결과는 7밖에 안나온다.
덧글
dfs(nR, nC, step+1) 아래에서 왜 visited를 0으로 만들어주는건가요?