[SW2105] 디저트 카페

 SW Expert Academy - 디저트 카페 

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu&categoryId=AV5VwAr6APYDFAWu&categoryType=CODE&problemTitle=sw&orderBy=PASS_RATE&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

문제 입출력

4                
9 8 9 8
4 6 9 4
8 7 7 8
4 5 3 5

#1 6

 

문제 풀이

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


public class Solution {
	static int ans, T, N, sy, sx;
	static int[][] map;
	static boolean[][] visit;
	static boolean[] tasted; // 이미 맛본 디저트

	// 우상 -> 우하 -> 좌하 -> 좌상
	static int[] dy = { -1, 1, 1, -1 };
	static int[] dx = { 1, 1, -1, -1 };

	static int[][] dyx = { { 0, 1 }, { 1, 2 }, { 2, 3 }, { 3, 0 } };

	static StringBuilder sb = new StringBuilder();


	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) map[i][j] = Integer.parseInt(st.nextToken());
				// System.out.println(Arrays.toString(map[i]));
			}

			// 초기화
			ans = -1;
			visit = new boolean[N][N];
			tasted = new boolean[101]; // 0 dummy

			// 탐색
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					sy = i;
					sx = j;
					dfs(i, j, 0, 0);
				}

			}

			// 출력
			sb.append("#").append(t).append(" ").append(ans).append("\n");

		}

		System.out.println(sb.toString());

	} // end main


	private static void dfs(int y, int x, int dir, int dep) {
		if (sy == y && sx == x && dir == 3) {
			ans = Math.max(ans, dep);
			return;
		}

		for (int d : dyx[dir]) {
			int ny = y + dy[d];
			int nx = x + dx[d];

			if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
			if (visit[ny][nx]) continue;
			if (tasted[map[ny][nx]]) continue;

			visit[ny][nx] = true;
			tasted[map[ny][nx]] = true;
			dfs(ny, nx, d, dep + 1);
			visit[ny][nx] = false;
			tasted[map[ny][nx]] = false;
		}

	} // end dfs

}

• 대각선 사각형을 도는 델타를 지정한다. (우상 -> 우하 -> 좌하 -> 좌상)
• 이게 사각형을 돌려면 자기 자신에서 앞으로 가거나 아니면 꺾는 방향으로 이어져야 한다.
• 즉슨 우상으로 갔다면, 앞으로 우상 혹은 우하 로 가야지만 사각형을 만들 수 있다.
• 그래서 dyx 라는 방향 배열을 초기화해준다.
• 그런 다음에 백트랙킹 해야하므로 visit, tasted 배열을 false 로 초기화 해주어야 한다.
• tasted 배열은 맛본 디저트의 종류를 저장하는 배열이다. 총 100 가지 라고 했으므로 0을 dummy 로 둬서 101가지로 선언.
• 그리고 사각형을 이룰 때 좌상으로 끝나야 하므로 기저조건에 dir == 3 을 넣어줘야 한다.
• 저거 안넣어주면 다 1이 된다. 왜냐하면 저 조건이 없으면 무조건 들어올 때 sy == y, sx == x 가 되므로.

 

 

 

 

 

 

 

 

 

# sw 디저트 카페 java # sw 디저트카페 dfs

---