dfs 로 풀이를 하는데, 갔던 넘버는 가지않고, 돌아와야 합니다. 오께이. 설계를 하고, 이것을 dfs 돌리면 됩니다. 여기서 하나 주의해야할 점은 dfs 안에 들어가 있는 변수는 글로벌 변수가 아닌 지역 변수를 사용해서 기존의 값들을 저장해야합니다. 글로벌으로 하면 연동이 되어, return 했을때의 값들을 잃어버리게 됩니다. 초기화도 어디서 시켜주어야 하는지 명확히 구분을 짓습니다. 사용이 끝나면 초기화해주는 것. 특히나 dfs 에서는 return 하는 곳과 return 하기전에 방문한 곳을 지워주는 것이 필요합니다. |
/* 갈 수 있는 곳까지 가고 3명의 방향전화을 한 뒤에, 갈 수 있는 곳 까지 가는 것은 와일문을 돌립니다. 만약에 depth 가 4가 되고 갈 수 있는 곳 까지 간다음에, 간 자리가 처음 시작한 자리에서 하나 이동한 자리라면 numArr 에서 1을 표시한 숫자를 나타내어 줍니다. */ #include <iostream> #include <algorithm> #define SIZE 21 // 21 #define SIZE2 101 // 101 using namespace std; int dx[] = {1,1,-1,-1}; int dy[] = {1,-1,-1,1}; // 아래오른쪽, 아래왼쪽, 위왼쪽, 위오른쪽 int ans; int N; int numArr[SIZE2]; int map[SIZE][SIZE]; int d, desert; int finalX, finalY; void problemIn() { cin >> N; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> map[i][j]; } /* (뎁스4)3번 방향전화하고 모든 while 문을 돌리고 (뎁스5)4번 시작하려고 할 때, 조사를 시작하면 됩니다. 맵에서 벗어나지 않고, 갔던 디저트 넘버가 아니면 */ void dfs(int x, int y, int depth){ if (depth == 4) { if (x == finalX && y == finalY) { // 돌아오는데 성공을 했으면, for (int i = 0; i < SIZE2; i++) { if (numArr[i] == 1) { desert++; } } ans = max(ans, desert); desert = 0; } return; } numArr[map[x][y]] = 1; int nx = x + dx[depth]; int ny = y + dy[depth]; if (nx >= 0 && ny >= 0 && nx < N && ny < N && numArr[map[nx][ny]]==0) { dfs(nx, ny, depth); dfs(nx, ny, depth + 1); } else { dfs(x, y, depth + 1); } numArr[map[x][y]] = 0; return; } void solve() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (i + 1 >= 0 && i + 1 < N && j + 1 >= 0 && j + 1 < N) { // 시작할 길이 있고, if (i + 1 >= 0 && i + 1 < N && j - 1 >= 0 && j - 1 < N) { //돌아오는 길이 있으면, finalX = i + 1; finalY = j - 1; dfs(i, j, 0); } } } } } int main() { int T; cin >> T; for (int tc = 1; tc <= T; tc++) { problemIn(); solve(); if (ans == 0) ans = -1; cout << "#" << tc << " " << ans << endl; ans = 0; } } |