[SWEA/모의 SW 역량테스트] 1949. 등산로 조성 - JAVA 자바

• 구현 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);
    }
}