SWEA 2105번
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu
방향 탐색을 통한 DFS, 백트래킹 문제이다.
대각선탐색을 활용할 수 있는 문제이다.
isVisited[i][j] = true;
isVisitedDesert[map[i][j]] = true;
DFS(i, j, i, j, 1, 0);
isVisitedDesert[map[i][j]] = false;
isVisited[i][j] = false;
백트래킹 문제이므로, 앞으로 나아갈 방향은 true를 해주고 다시 돌아왔을 때는 false값을 준다.
for (int i = index; i < 4; i++) {
int nowX = x + dirX[i];
int nowY = y + dirY[i];
// 시작한 곳으로 돌아오면 중지, 재귀 탈출 조건
// counting이 3이상이고, counting이 짝수.
if (startX == nowX && startY == nowY && counting >= 4) {
maxResult = Math.max(maxResult, counting);
return;
}
// 만약 i의 값으로 계속 이동할 수 있으면 계속해서 이동.
if (rangeCheck(nowX, nowY) && !isVisited[nowX][nowY] && !isVisitedDesert[map[nowX][nowY]]) {
isVisited[nowX][nowY] = true;
isVisitedDesert[map[nowX][nowY]] = true;
DFS(startX, startY, nowX, nowY, counting + 1, i);
isVisitedDesert[map[nowX][nowY]] = false;
isVisited[nowX][nowY] = false;
}
}
탐색을 하면서 답을 얻어내는 과정은 조건을 주면 된다.
출발한 곳을 방문할 수 있을 때 & 디저트 개수를 담은 counting
변수가 4이상 일 때 모든 조건을 완수한 것이므로 결과값을 담을 maxResult
와 최댓값 비교를 해서 결과를 얻으면 된다.
가지치기 조건은 단순한데, 배열을 벗어나지 않아야 하고, 이미 방문을 한 곳은 당연히 갈 필요가 없다
디저트가 겹치는 곳도 갈 필요가 없기 때문에, 현재 가지고 있는 디저트 여부를 isVisitedDesert
를 통해서 체크한다
디저트의 숫자가 곧 index가 되어 해당 자리가 true일 경우 이미 가지고 있는 디저트로 간주하여 가지치기를 해줄 수 있다.
import java.util.*;
import java.io.*;
// 디저트를 가장 많이 먹을 수 있는 경우의 디저트 종류 수를 출력
// 디저트를 먹을 수 없는 경우 -1을 출력
// 탐색하는 방향에서 직사각형의 특징을 생각해야 됨 -> 직사각형의 특징. 마주보는 변의 길이가 같음
public class Solution {
static int N;
static int[][] map;
static int[] dirX = {-1, 1, 1, -1}; // 대각선 방향으로 시계방향. (상우 -> 하우 -> 하좌 -> 상좌)
static int[] dirY = {1, 1, -1, -1};
static boolean[][] isVisited; // map의 경로상 방문여부를 체크하는 배열
static boolean[] isVisitedDesert; // 방문한 디저트가 겹치는지 여부를 파악하기 위한 배열
static int maxResult;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for (int t = 1; t <= T; t++) {
sb.append('#').append(t).append(' ');
N = Integer.parseInt(br.readLine());
init(); // 변수 초기화
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());
}
}
// 완전탐색 & 백트래킹
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i == 0 && (j == 0 || j == N - 1)) continue;
else if (i == N - 1 && (j == 0 || j == N - 1)) continue;
isVisited[i][j] = true;
isVisitedDesert[map[i][j]] = true;
DFS(i, j, i, j, 1, 0);
isVisitedDesert[map[i][j]] = false;
isVisited[i][j] = false;
}
}
sb.append(maxResult).append('\n');
}
bw.write(sb.toString());
bw.close();
} // End of main
private static void DFS(int startX, int startY, int x, int y, int counting, int index) {
for (int i = index; i < 4; i++) {
int nowX = x + dirX[i];
int nowY = y + dirY[i];
// 재귀 탈출 조건
// counting이 4이상이고, 시작한 곳으로 돌아오면 중지,
if (startX == nowX && startY == nowY && counting >= 4) {
maxResult = Math.max(maxResult, counting);
return;
}
// 만약 i의 값으로 계속 이동할 수 있으면 계속해서 이동.
if (rangeCheck(nowX, nowY) && !isVisited[nowX][nowY] && !isVisitedDesert[map[nowX][nowY]]) {
isVisited[nowX][nowY] = true;
isVisitedDesert[map[nowX][nowY]] = true;
// 만약 i의 값으로 계속 이동할 수 있으면 계속해서 이동.
DFS(startX, startY, nowX, nowY, counting + 1, i);
isVisitedDesert[map[nowX][nowY]] = false;
isVisited[nowX][nowY] = false;
}
}
} // End of DFS
private static boolean rangeCheck(int nowX, int nowY) {
return nowX >= 0 && nowX < N && nowY >= 0 && nowY < N;
} // End of rangeCheck
private static void init() { // 변수를 초기화 하는 메소드
map = new int[N][N];
isVisited = new boolean[N][N];
isVisitedDesert = new boolean[101];
maxResult = -1;
} // End of init
} // End of Main class