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
728x90
'✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺 > SW Expert Academy' 카테고리의 다른 글
[SW7465] 창용 마을 무리의 개수 (0) | 2022.10.02 |
---|---|
[SW5656] 벽돌 깨기 (0) | 2022.10.02 |
[SW4008] 숫자 만들기 (0) | 2022.09.29 |
[SW5658] 보물상자 비밀번호 (0) | 2022.09.27 |
[SW2115] 벌꿀 채취 (0) | 2022.09.27 |