대각선으로 사방탐색을 하는 문제다.
주의해야할 조건은
- 같은 숫자의 디저트를 만나면 안된다.
- 시작점을 제외하고 이미 방문했던 곳은 다시 방문할 수 없다.
- 시작점으로 돌아오도록 사각형이 그려져야 한다.
- 최대한 많은 디저트를 먹어야 한다.
map의 좌표가 N일 때, 대각선으로 투어를 해야하기 때문에 양 끝 꼭짓점에서는 순회를 시작할 수 없다.
가장 큰 사각형의 가로 세로의 합은 N-1이다.
위 사진에서 N은 5고, 두 사각형이 가능한 최대 길이의 사각형이다.
왼쪽의 경우 가로가 3, 세로가 1이고 오른쪽은 가로가 2, 세로가 2다.
일직선이나 자기 자신만 투어하는 경우는 불가능하기 때문에 사각형의 한 변의 최소 길이는 1, 최대 길이는 N-2가 될 것이다.
이를 활용해서 두 변의 길이의 합이 최대일 때부터 최소일 때까지를 순회하며 dfs를 진행하였다.
만약 dfs를 통해 가능한 경우의 수를 찾았다면 그 때가 최대 길이기 때문에 그 길이를 답으로 정하면 된다.
out: for (int sum = N - 1; sum >= 2; sum--) {
for (int x = sum - 1; x >= 1; x--) {
int y = sum - x;
// x=row, y=col
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
// 시작지점 저장하기
sr = i;
sc = j;
find(x, y, i, j, 0, 0);
if (ans != -1)
break out;
list.clear();
}
}
}
dfs의 종료 조건을 구체화하기 위해 sum에 따라 가능한 x(row), y(col)의 변의 길이를 정하고 이에 따라 dfs를 구현하였다.
// 시작 지점으로 돌아왔다면 답 구하기
if (x * 2 == dx && y * 2 == dy && r == sr && c == sc) {
ans = Math.max((x + y) * 2, ans);
return;
}
if (!(r == sr && c == sc) && visited[r][c])
return; // 시작지점이 아닌데 다시 방문한 좌표에 돌아오면 return
// 이미 방문한 숫자면 return
for (int i = 0; i < list.size(); i++) {
if (list.get(i) == map[r][c])
return;
}
x와 y만큼 모든 방향을 순회하고 시작 지점에 돌아왔을 때는 사각형이 만들어진 것이므로 답을 업데이트한다.
시작 지점이 아닌데 다시 방문한 좌표에 돌아왔다면 함수를 종료한다.
또한 list에 방문한 위치의 값들을 추가하여 방문한 디저트의 숫자와 같다면 함수를 종료한다.
visited[r][c] = true;
list.add(map[r][c]);
// depth는 x부터 시작함
int nr = r;
int nc = c;
int d = 0;
// dx랑 dy를 더해주기
if (dx < x) {
d = 0;
dx += 1;
} else if (dy < y) {
d = 1;
dy += 1;
} else if (dx < 2 * x) {
d = 2;
dx += 1;
} else if (dy < 2 * y) {
d = 3;
dy += 1;
}
nr = r + dr[d];
nc = c + dc[d];
if (nr >= 0 && nr < N && nc >= 0 && nc < N) // 해당 방향을 충족하는 경우에만 dfs 계속
find(x, y, nr, nc, dx, dy);
visited[r][c] = false;
종료 조건이 아닌 경우에는 방문 처리를 하고, 해당 값을 리스트에 추가한다.
dx와 dy는 row와 col이 얼마만큼 이동했는지를 의미한다.
dx와 dy를 x, y와 비교해서 어떤 방향으로 가야할지를 정했다.
그렇게 정한 좌표가 배열의 범위를 벗어난다면 해당 위치에서는 사각형을 그릴 수 없음을 의미하기 때문에 범위 안에 있는 경우에만 함수를 실행하도록 구현하였다.
전체 코드
package 모의sw;
import java.util.ArrayList;
import java.util.Scanner;
public class SWEA_2105_디저트카페 {
static int N;
static int[][] map;
static int[] dr = { 1, 1, -1, -1 };
static int[] dc = { 1, -1, -1, 1 };
static int sr, sc;
static boolean[][] visited;
static ArrayList<Integer> list;
static int ans = 0;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int T = scan.nextInt();
for (int t = 1; t <= T; t++) {
N = scan.nextInt();
ans = -1;
map = new int[N][N];
visited = new boolean[N][N];
list = new ArrayList<>();
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
map[i][j] = scan.nextInt();
// 가능한 길이의 조합 -> 최대를 구해야하니까 n-1부터 시작하기
// 답은 가로+세로 길이 *2 -> 사각형의 둘레
// 길이의 최소는 1+1
out: for (int sum = N - 1; sum >= 2; sum--) {
for (int x = sum - 1; x >= 1; x--) {
int y = sum - x;
// x=row, y=col
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
// 시작지점 저장하기
sr = i;
sc = j;
find(x, y, i, j, 0, 0);
if (ans != -1)
break out;
list.clear();
}
}
}
System.out.println("#" + t + " " + ans);
}
}
static void find(int x, int y, int r, int c, int dx, int dy) {
// 시작 지점으로 돌아왔다면 답 구하기
if (x * 2 == dx && y * 2 == dy && r == sr && c == sc) {
ans = Math.max((x + y) * 2, ans);
return;
}
if (!(r == sr && c == sc) && visited[r][c])
return; // 시작지점이 아닌데 다시 방문한 좌표에 돌아오면 return
// 이미 방문한 숫자면 return
for (int i = 0; i < list.size(); i++) {
if (list.get(i) == map[r][c])
return;
}
visited[r][c] = true;
list.add(map[r][c]);
// depth는 x부터 시작함
int nr = r;
int nc = c;
int d = 0;
// dx랑 dy를 더해주기
if (dx < x) {
d = 0;
dx += 1;
} else if (dy < y) {
d = 1;
dy += 1;
} else if (dx < 2 * x) {
d = 2;
dx += 1;
} else if (dy < 2 * y) {
d = 3;
dy += 1;
}
nr = r + dr[d];
nc = c + dc[d];
if (nr >= 0 && nr < N && nc >= 0 && nc < N) // 해당 방향을 충족하는 경우에만 dfs 계속
find(x, y, nr, nc, dx, dy);
visited[r][c] = false;
}
}
'문제 풀이 > SWEA' 카테고리의 다른 글
[SWEA] [모의 SW 역량테스트] 5656 - 벽돌 깨기 (자바 Java) (1) | 2022.09.29 |
---|---|
[SWEA] 1767 - 프로세서 연결하기 (자바/Java) (1) | 2022.09.23 |
[SWEA] 4008 - 숫자 만들기 (자바/Java) (0) | 2022.09.22 |
[SWEA] 2819 - 격자판의 숫자 이어 붙이기 (0) | 2022.08.25 |
[SWEA] 1231 - 중위 순회 (0) | 2022.08.23 |