[SWEA 1949번] 등산로 조성 :: 늦깎이 IT

[SWEA 1949. [모의 SW 역량테스트] 등산로 조성 URL]

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq&categoryId=AV5PoOKKAPIDFAUq&categoryType=CODE

1. 최대값을 찾는다.

2. 최대값부터 DFS 탐색을 시작한다.

3. DFS는 등산로의 길이와 공사 여부를 매개변수로 받는다.

4. DFS 탐색시, 현재 위치와 다음 위치의 높이를 비교한다.

 - 현재 위치가 다음 위치보다 높다면, 다시 DFS 메소드를 호출한다. 여기서 주의할점은 다음 탐색시, 공사여부는

   현재 공사여부의 값을 매개변수로 받는다. (현재 공사여부 = 다음 공사여부)

 - 현재 위치가 다음 위치보다 높지않고 이제까지 공사를 한번도 하지 않았다면 공사를 시작한다.

   공사할 때 팔 수 있는 깊이는(1~K)이다. 지형을 깎을 높이를 정했으면(1~K), 그 높이만큼 지형을 깎은 후에 

   탐색을 시작한다. 여기서 주의할 점은, 다음 탐색시 공사여부는 True(공사를 했음)을 매개변수로 받는다.

[소스 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.concurrent.LinkedBlockingDeque;
 
public class Solution {
 
    public static int N, K, tCase, maxVal, ans;
    public static int[][] map;
    public static boolean[][] visited;
    public static int[] dirX = new int[] { 0, 0, 1, -1 }; // 동서남북
    public static int[] dirY = new int[] { 1, -1, 0, 0 };
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static void main(String[] args) throws NumberFormatException, IOException {
 
        tCase = Integer.parseInt(br.readLine());
 
        for (int t = 1; t <= tCase; t++) {
 
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
 
            ans = maxVal = Integer.MIN_VALUE;
            map = new int[N][N];
            visited = new boolean[N][N];
 
            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());
                    maxVal = Math.max(maxVal, map[i][j]);
                }
            }
 
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (map[i][j] == maxVal) {
                        dfs(i, j, 1, false);
                    }
                }
            }
 
            System.out.println("#" + t + " " + ans);
        }
    }
 
    public static void dfs(int row, int col, int cnt, boolean used) {
 
        visited[row][col] = true;
 
        for (int i = 0; i < 4; i++) {
 
            int nr = row + dirX[i];
            int nc = col + dirY[i];
 
            if (isBoundary(nr, nc) && !visited[nr][nc]) {
                if (map[nr][nc] < map[row][col]) {
 
                    dfs(nr, nc, cnt + 1, used);
                } else {
                    if (!used) {
                        for (int j = 1; j <= K; j++) {
                            if (map[nr][nc] - j < map[row][col]) {
                                map[nr][nc] -= j;
                                dfs(nr, nc, cnt + 1, true);
                                map[nr][nc] += j;
                            }
                        }
                    }
                }
            }
        }
        visited[row][col] = false;
        ans = Math.max(ans, cnt);
 
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < N) && (col >= 0 && col < N);
    }
 
    public static void showMap(int[][] map) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
}
 
class Node {
    int row;
    int col;
    int cnt;
 
    public Node(int row, int col, int cnt) {
        this.row = row;
        this.col = col;
        this.cnt = cnt;
    }
 
}