[SWEA][Java][모의 SW][DFS] 2105 - 디저트 카페

친구들과 디저트 카페 투어를 할 계획이다.

[Fig. 1]과 같이 한 변의 길이가 N인 정사각형 모양을 가진 지역에 디저트 카페가 모여 있다.

원 안의 숫자는 해당 디저트 카페에서 팔고 있는 디저트의 종류를 의미하고

카페들 사이에는 대각선 방향으로 움직일 수 있는 길들이 있다.

디저트 카페 투어는 어느 한 카페에서 출발하여

[Fig. 2]와 같이 대각선 방향으로 움직이고 사각형 모양을 그리며 출발한 카페로 돌아와야 한다.
 
 

디저트 카페 투어를 하는 도중 해당 지역을 벗어나면 안 된다.

또한, 친구들은 같은 종류의 디저트를 다시 먹는 것을 싫어한다.

즉, [Fig. 3]과 같이 카페 투어 중에 같은 숫자의 디저트를 팔고 있는 카페가 있으면 안 된다.
 
 

[Fig. 4]와 같이 하나의 카페에서 디저트를 먹는 것도 안 된다.

 

[Fig. 5]와 같이 왔던 길을 다시 돌아가는 것도 안 된다.
 

 

친구들과 디저트를 되도록 많이 먹으려고 한다.

디저트 가게가 모여있는 지역의 한 변의 길이 N과 디저트 카페의 디저트 종류가 입력으로 주어질 때,

임의의 한 카페에서 출발하여 대각선 방향으로 움직이고

서로 다른 디저트를 먹으면서 사각형 모양을 그리며 다시 출발점으로 돌아오는 경우,

디저트를 가장 많이 먹을 수 있는 경로를 찾고, 그 때의 디저트 수를 정답으로 출력하는 프로그램을 작성하라.

만약, 디저트를 먹을 수 없는 경우 -1을 출력한다.


[예시]

한 변의 길이 N이 4인 지역에 디저트 카페가 [Fig. 6]과 같이 있다고 생각하자.
 

디저트 카페 투어가 가능한 경우는 [Fig. 7]과 같이 5가지로 나눌 수 있다.

(출발한 곳과 도는 방향은 다를 수 있지만, 디저트 카페 투어의 경로가 그리는 사각형 모양은 5가지 중 하나이다.)

 

[Fig. 7]

 
이 중에 디저트를 가장 많이 먹을 수 있는 경우는 ⑤인 경우로 디저트의 종류는 6개이다.

따라서, 정답은 6이 된다.


[제약사항]

1. 시간제한 : 최대 50개 테스트 케이스를 모두 통과하는 데 C/C++/Java 모두 3초

2. 디저트 카페가 모여있는 지역의 한 변의 길이 N은 4 이상 20 이하의 정수이다. (4 ≤ N ≤ 20)

3. 디저트 종류를 나타나는 수는 1 이상 100 이하의 정수이다.


[입력]

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 디저트 카페가 모여있는 지역의 한 변의 길이 N이 주어진다.

그 다음 N 줄에는 N * N 크기의 디저트 카페에서 팔고 있는 디저트 종류에 대한 정보가 주어진다.


[출력]

테스트 케이스 개수만큼 T개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.

각 줄은 "#t"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (t는 1부터 시작하는 테스트 케이스의 번호이다)

출력해야 할 정답은 가능한 경우 중 디저트를 가장 많이 먹을 때의 디저트 수 이다.

만약, 디저트를 먹을 수 없는 경우 정답은 -1이다.

 

---

🌈 풀이 후기

• 일반적인 DFS와 다른 점은 이전의 방향을 기억해야 한다는 점. 방향이 상하좌우가 아니라 대각선이라는 점이다.
• 이전의 방향을 같이 보내서 그 방향 다음 방향만 찾도록 한다. 
  
  * 왼쪽 아래 대각선으로 내려간 경우 오른쪽 대각선으로 내려갈 수 없도록 하기 위해서.

👩‍🏫 문제 풀이

1.  최소 양옆이 있어야하고 밑에 2칸까지는 여유가 있어야 사각형이 만들어 지기 때문에 미리 조건 처리해준다. 
2. 먹은 디저트를 방문처리 하고 위치도 함께 방문처리 해준다. ( 둘다 중복이면 안되기 때문에)
3. dfs를 돌면서 이전의 방향 다음 방향만 탐색하도록 해준다.
4. 만약 자기 자신한테 돌아온 경우 (최소 3번 이상 탐색해서) 종료시켜주고 max를 비교해준다.

package SWTest;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class SWEA_SWTEST_디저트카페 {
	static int N;
	static int[][] map;
	static int[] dr = { 1, 1, -1, -1 }; // 우하 좌하 좌상 우상
	static int[] dc = { 1, -1, -1, 1 };
	static boolean[][] visit;
	static boolean[] dessert;
	static int max = 0;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringTokenizer st;

		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			max = 0;
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < N; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			// 양옆과 밑에 2칸이 있어야 사각형 가능
			for (int i = 0; i < N - 2; i++) {
				for (int j = 1; j < N - 1; j++) {
					visit = new boolean[N][N];
					dessert = new boolean[101];
					visit[i][j] = true;
					dessert[map[i][j]] = true;
					dfs(1, i, j, i, j, 0);
				}
			}

			if (max == 0)
				max = -1;
			System.out.println("#" + tc + " " + max);
		}

	}

	private static void dfs(int cnt, int r, int c, int initR, int initC, int prevD) {
		
		// preD : 이전 방향을 넘겨서 그 방향보다 같거나 다음 방향으로만 향한다. 그 전 방향으로는 이동 X. 
		for (int i = prevD; i < 4; i++) {
			int nr = r + dr[i];
			int nc = c + dc[i];

			if (nr >= 0 && nr < N && nc >= 0 && nc < N) {
				if ((nr == initR) && (nc == initC) && cnt > 2) {

					max = Math.max(max, cnt);
					return;
					// 종료
				}
				if (!visit[nr][nc] && !dessert[map[nr][nc]]) {
					visit[nr][nc] = true;
					dessert[map[nr][nc]] = true;
					dfs(cnt + 1, nr, nc, initR, initC, i);
					visit[nr][nc] = false;
					dessert[map[nr][nc]] = false;
				}

			}

		}
	}

}