SWEA 1949번
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq
문제
생각하기
-
백트래킹 문제이다.
- 등산로를 찾는 과정에서 갈 수 있는 모든 방향을 찾기위해서 백트래킹을 사용해야 한다.
-
부트르포스가 아닌 이유는, 최고 높이를 기준으로 찾아가도 정답을 찾을 수 있기 때문이다.
동작
int maxHeight = -1;
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());
maxHeight = Math.max(map[i][j], maxHeight);
}
}
map을 만들면서 최고 봉우리 높이를 찾아서 maxHeight에 저장한다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (maxHeight != map[i][j]) continue;
isVisited[i][j] = true;
DFS(i, j, 1, map[i][j], K);
isVisited[i][j] = false;
}
}
이제 maxHeight일 경우에만 DFS탐색을 시작한다. (등산로 탐색)
private static void DFS(int x, int y, int length, int height, int k) {
DFS의 매개 변수 x, y는 좌표값으로 사용되고, length는 등산로의 길이를 재귀로 넘겨줄 변수이다.
height는 현재 등산로의 높이값을 저장할 변수이고 k는 등산로를 깎을 수 있는 높이를 넣어주는데,
이 k가 0이나 0이 아니냐로 구분하여 현재 내가 등산로를 깎을 수 있는지 없는지를 구분할 것이다.
문제에서 등산로는 딱 한번 깎을 수 있다는 조건이 있으므로 k가 0이냐 0이 아니냐의 조건으로 깎아서 갈 수 있냐 없냐를 구분하는 것이다.
private static void DFS(int x, int y, int length, int height, int k) {
// 최대 길이를 매번 갱신.
result = Math.max(length, result);
for (int i = 0; i < 4; i++) {
int nowX = dirX[i] + x;
int nowY = dirY[i] + y;
if (!rangeCheck(nowX, nowY) || isVisited[nowX][nowY]) continue;
if (k == 0) {
if (map[nowX][nowY] < height) {
isVisited[nowX][nowY] = true;
DFS(nowX, nowY, length + 1, map[nowX][nowY], k);
isVisited[nowX][nowY] = false;
}
} else {
if (map[nowX][nowY] < height) {
isVisited[nowX][nowY] = true;
DFS(nowX, nowY, length + 1, map[nowX][nowY], k);
isVisited[nowX][nowY] = false;
} else if ((map[nowX][nowY] - k) < height) {
// 앞으로 가려고 하는 곳의 높이가. K만큼 깎았을 때, height 보다 낮을 경우 갈 수 있음
// map[nowX][nowY]가 갈 수 있다는 조건에서 높이가 딱 1차이만 나도록 깎아야함
isVisited[nowX][nowY] = true;
DFS(nowX, nowY, length + 1, height - 1, 0);
isVisited[nowX][nowY] = false;
}
}
}
} // End of DFS
전체 DFS를 설명하자면, 매개변수 파트는 위에서 설명했고,
메소드가 시작되자 마자 result = Math.max(length, result); 해당 코드를 통해서 등산로 최고길이를 계속해서 갱신하게 된다.
DFS는 먼저 2가지 조건으로 구분 짓는다.
k가 0이나 0이 아니냐, 즉 내가 지금 등산로를 깎을 수 있냐 없냐 조건이다.
k가 0일 때는 등산로를 깎을 수 없기 때문에 오로지 height 보다 낮은 곳으로만 DFS를 실행하고,
k가 0이 아닐 때는 등산로를 깎을 수 있기 때문에 진행하려는 방향의 높이에서 k를 뺐을 때 즉,map[nowX][nowY] - k 가 현재 높이 height보다 작을 경우 갈 수 있다고 판단하고 DFS를 실행한다.
단, 여기서 등산로를 딱 한번 깎을 수 있다는 조건을 사용하였기 때문에 다음 DFS에서는 k를 0으로 주고 DFS를 실행한다.
또 k가 0이 아닌 경우에서도 높이가 낮으면 진행할 수 있기 때문에 height보다 낮은 높이를 찾아서 DFS를 실행하도록 했다.
해당 3가지 경우를 생각하면 가장 긴 등산로를 찾아서 결괏값을 찾을 수 있게된다.
코드
Java
import java.util.*;
import java.io.*;
public class Solution {
static int N, K, result;
static int[][] map;
static boolean[][] isVisited;
static int[] dirX = {-1, 1, 0, 0};
static int[] dirY = {0, 0, -1, 1};
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();
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
for (int t = 1; t <= T; t++) {
sb.append('#').append(t).append(' ');
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
init();
int maxHeight = -1;
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());
maxHeight = Math.max(map[i][j], maxHeight);
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (maxHeight != map[i][j]) continue;
isVisited[i][j] = true;
DFS(i, j, 1, map[i][j], K);
isVisited[i][j] = false;
}
}
sb.append(result).append('\n');
}
bw.write(sb.toString());
bw.close();
} // End of main
// 백트래킹을 통해서 등산로를 깎으면서 갈 수 있는 모든 길을 다 가봄.
private static void DFS(int x, int y, int length, int height, int k) {
// 최대 길이를 매번 갱신.
result = Math.max(length, result);
for (int i = 0; i < 4; i++) {
int nowX = dirX[i] + x;
int nowY = dirY[i] + y;
if (!rangeCheck(nowX, nowY) || isVisited[nowX][nowY]) continue;
if (k == 0) {
if (map[nowX][nowY] < height) {
isVisited[nowX][nowY] = true;
DFS(nowX, nowY, length + 1, map[nowX][nowY], k);
isVisited[nowX][nowY] = false;
}
} else {
if (map[nowX][nowY] < height) {
isVisited[nowX][nowY] = true;
DFS(nowX, nowY, length + 1, map[nowX][nowY], k);
isVisited[nowX][nowY] = false;
} else if ((map[nowX][nowY] - k) < height) {
// 앞으로 가려고 하는 곳의 높이가. K만큼 깎았을 때, height 보다 낮을 경우 갈 수 있음
// map[nowX][nowY]가 갈 수 있다는 조건에서 높이가 딱 1차이만 나도록 깎아야함
isVisited[nowX][nowY] = true;
DFS(nowX, nowY, length + 1, height - 1, 0);
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];
result = -1;
} // End of init
} // End of Main class
