등산로 조성[모의 SW 역량테스트] (자바)
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
이 문제에서 가장 핵심인 곳은 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K깊이 만큼 지형을 깎을 수 있다는 점이다.
K=4가 주어지면 이걸 1,1,1,1 or 1,1,2 이렇게 나눠서 깎는 것이 아니고 한 지점을 정해서 1~4까지 깎을 수 있는 것이다.
전체 코드를 우선 확인하자.
import java.util.Scanner;
public class Solution {
static int[][] map;
static boolean[][] visited;
static int K;
static int N;
static int[] dr = { -1, 1, 0, 0 };
static int[] dc = { 0, 0, -1, 1 };
static int max;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
max = Integer.MIN_VALUE;
N = sc.nextInt();
K = sc.nextInt(); // 땅파기
map = new int[N][N];
visited = new boolean[N][N]; // 방문체크
int maxheight = 0; // 최대 봉우리
// 봉우리 입력, 최대 봉우리 찾기
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
map[i][j] = sc.nextInt();
if (maxheight < map[i][j])
maxheight = map[i][j];
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == maxheight) { // 최대 봉우리면 시작
DFS(i, j, 1, false); // 우선 땅을 안팠다고 주고 dfs 시작
}
}
}
System.out.printf("#%d %d\n",tc,max);
}
}
public static void DFS(int x, int y, int cnt, boolean dig) {
visited[x][y] = true;
if(cnt>max) max = cnt;
for (int i = 0; i < 4; i++) {
int idx = x + dr[i];
int idy = y + dc[i];
if (idx >= 0 && idy >= 0 && idx < N && idy < N) {
// 안파고 가도 되는 경우
if (!visited[idx][idy] && map[x][y] > map[idx][idy]) {
DFS(idx, idy, cnt + 1, dig); // dig는 변경이 없으니 그대로 넘긴다.
}
// 다음 봉우리가 더 높거나 같다면
else if (map[x][y] <= map[idx][idy]) {
// 방문 안 했고, 안 팠고, K만큼 팠을 때 작아지면
if(!visited[idx][idy] && !dig && map[x][y] > map[idx][idy]-K) {
int temp = map[idx][idy]; // 임시로 저장해놔야 돌아올 때 원상복구
for(int j=1; j<=K; j++) { // 1부터 K까지 볼 건데
if(map[idx][idy]-j < map[x][y]) { // j를 뺐을 때 map[x][y]가 크면
map[idx][idy]-=j; // 빼고
DFS(idx, idy, cnt + 1, true); // 팠다고 하고 DFS돈다.
map[idx][idy] = temp; // 다시 원상복구
}
}
}
}
}
}
visited[x][y] = false;
}
}
지금부터 코드를 하나 살펴보겠다.
static int[][] map; // 입력받을 맵
static boolean[][] visited; // 방문체크
static int K; // 최대 공사 횟수
static int N; // 맵의 크기
// 상, 하, 좌, 우를 탐색하기 위한 배열
static int[] dr = { -1, 1, 0, 0 };
static int[] dc = { 0, 0, -1, 1 };
// 최대값 찾기
static int max;스태틱으로 선언해서 사용하도록 만들었다.
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
max = Integer.MIN_VALUE;
N = sc.nextInt();
K = sc.nextInt(); // 땅파기
map = new int[N][N];
visited = new boolean[N][N]; // 방문체크
int maxheight = 0; // 최대 봉우리
// 봉우리 입력, 최대 봉우리 찾기
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
map[i][j] = sc.nextInt();
if (maxheight < map[i][j])
maxheight = map[i][j];
}
}최대 봉우리 변수를 생성하고 입력을 넣음과 동시에 최대 봉우리를 찾게 만들었다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == maxheight) { // 최대 봉우리면 시작
DFS(i, j, 1, false); // 우선 땅을 안팠다고 주고 dfs 시작
}
}
}
System.out.printf("#%d %d\n",tc,max);
}
}전체를 탐색하면서 최대봉우리면 DFS를 돌게 만들었다.
DFS에는 i,j의 좌표, 땅 시작 번호, boolean으로 땅을 팠는지 안 팠는지 신호를 같이 주었다.
false면 땅을 안 판 상태고, true면 땅을 판 상태이다.
public static void DFS(int x, int y, int cnt, boolean dig) {
visited[x][y] = true;
if(cnt>max) max = cnt;
for (int i = 0; i < 4; i++) {
int idx = x + dr[i];
int idy = y + dc[i];
if (idx >= 0 && idy >= 0 && idx < N && idy < N) {
// 안파고 가도 되는 경우
if (!visited[idx][idy] && map[x][y] > map[idx][idy]) {
DFS(idx, idy, cnt + 1, dig); // dig는 변경이 없으니 그대로 넘긴다.
}DFS는 우선 방문 처리를 하고 max와 cnt를 비교해서 갱신을 해준다.
이후에 사방탐색을 돌기 위해 for문을 작성했다.
먼저 범위 안에 있는지 확인하고 조건을 나눠야 한다.
1. 땅을 안 파도 내려갈 수 있는 경우
DFS에 cnt+1과 땅을 파지 않았으니 dig를 그대로 넘긴다. 현재 dig는 false다.
// 다음 봉우리가 더 높거나 같다면
else if (map[x][y] <= map[idx][idy]) {
// 방문 안 했고, 안 팠고, K만큼 팠을 때 작아지면
if(!visited[idx][idy] && !dig && map[x][y] > map[idx][idy]-K) {
int temp = map[idx][idy]; // 임시로 저장해놔야 돌아올 때 원상복구
for(int j=1; j<=K; j++) { // 1부터 K까지 볼 건데
if(map[idx][idy]-j < map[x][y]) { // j를 뺐을 때 map[x][y]가 크면
map[idx][idy]-=j; // 빼고
DFS(idx, idy, cnt + 1, true); // 팠다고 하고 DFS돈다.
map[idx][idy] = temp; // 다시 원상복구
}
}
}
}
}
}
visited[x][y] = false;
}
}2. 다음 봉우리가 더 높은 상태인데 K를 파면 내려갈 수 있는 경우
방문도 하지 않았고, dig==fasle이고, 이동했던 맵에서 K만큼 빼면 이전 맵보다 큰 경우 진행이 가능하다.
우선 맵을 원상복구를 해야하기 때문에 temp에 해당 지점의 값을 저장해놓는다.
바로 K를 빼도 되지만 K미만 뺐을 때 최적이 되는 경우가 있어서 1부터 K까지 전부 살펴보는 방법을 택했다.
j만큼 뺀 다음에 DFS를 true로 바꿔서 넘기면 된다.
!! 다시 되돌아오면 temp에 저장했던 값을 이용해 원상복구를 진행한다. !!
그리고 for문이 끝나면 false로 만들어준다.
전형적인 DFS문제이다.