Algorithm/Problem Solving
[SWEA/모의 SW 역량테스트] 1949. 등산로 조성 - JAVA 자바
gangintheremark
2024. 2. 21. 23:13
728x90
구현
DFS
가장 높은 봉우리에서 시작하여 가장 긴 등산로를 찾아 길이를 출력하는 문제이다. 이 때, 딱 한 곳을 최대 K 깊이만큼 깎을 수 있다는 옵션이 있다.
가장 높은 봉우리 좌표에서 시작하여 상하좌우 탐색하며 처음으로 이전 봉우리보다 큰 봉우리를 만난 경우, 1 ~ K 깊이로 깎아 이전 봉우리보다 작아지면 이어서 탐색할 수 있도록 한다. 딱 한 곳만 깎을 수 있으므로 한 번 깎았다면 탐색 중 큰 봉우리를 만나도 지나갈 수 없다.
1. 이전 봉우리보다 낮으면 방문처리 후 재귀
2. 이전 봉우리보다 높으면서 한 곳 깎을 수 있는 경우
2-1. 이전 봉우리보다 낮아질 때 까지 깎기 ( 최대 K )
2-2. 낮아지면 방문처리 및 깎는 공사를 한 번 진행했으므로 flag = true
3. 백트래킹
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Solution {
static int n, k, result;
static boolean flag;
static int[][] board;
static boolean[][] visited;
static int[] dx = { 1, -1, 0, 0 };
static int[] dy = { 0, 0, 1, -1 };
public static void dfs(int x, int y, int count) {
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny]) {
if (board[nx][ny] >= board[x][y] && !flag) {
for (int j = 1; j <= k; j++) {
board[nx][ny] -= j;
if (board[nx][ny] < board[x][y]) {
visited[nx][ny] = true;
flag = true;
dfs(nx, ny, count + 1);
visited[nx][ny] = false;
flag = false;
board[nx][ny] += j;
continue;
}
board[nx][ny] += j;
}
} else if (board[nx][ny] < board[x][y]) {
visited[nx][ny] = true;
dfs(nx, ny, count + 1);
visited[nx][ny] = false;
}
} else {
result = Math.max(result, count);
}
}
}
public static void main(String[] args) throws NumberFormatException, IOException {
// System.setIn(new FileInputStream("sample_input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
for (int t = 1; t <= T; t++) {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
board = new int[n][n];
visited = new boolean[n][n];
result = 0;
int max = 0;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
max = Math.max(max, board[i][j]);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == max) {
// 가장 높은 봉우리를 기준으로 상하좌우 탐색
visited[i][j] = true;
dfs(i, j, 1);
visited[i][j] = false;
}
}
}
sb.append('#').append(t).append(' ').append(result).append('\n');
}
System.out.println(sb);
}
}
728x90