등산로 조성


Software Expert Academy [1949] 등산로 조성

문제보기
Alt text

풀이

  • dfs

소스코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Solution {
    static int N, K, ans;
    static int[][] map;
    static Queue<int[]> queue;
    static int[] dx = { 0, 0, -1, 1 };
    static int[] dy = { -1, 1, 0, 0 };
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
 
        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt();
            K = sc.nextInt();
            map = new int[N][N];
            ans = 1;
 
            int top = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    map[i][j] = sc.nextInt();
                    top = Math.max(top, map[i][j]);
                }
            }
 
            findTop(top);
            System.out.println("#" + tc + " " + ans);
        }
    }
 
    public static void findTop(int top) {
        queue = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == top) {
                    queue.add(new int[] { i, j });
                }
            }
        }
 
        while (!queue.isEmpty()) {
            int[] rc = queue.poll();
            boolean[][] visited = new boolean[N][N];
            visited[rc[0]][rc[1]] = true;
            findLoad(rc, 1, false, visited);
        }
    }
 
    public static void findLoad(int[] rc, int length, boolean flag, boolean[][] v) {
        for (int k = 0; k < 4; k++) {
            int x = rc[0] + dx[k];
            int y = rc[1] + dy[k];
 
            if (isRange(x, y) && !v[x][y]) {
                if (map[rc[0]][rc[1]] > map[x][y]) {
                    v[x][y] = true;
                    findLoad(new int[] { x, y }, length + 1, flag, v);
                    v[x][y] = false;
                } else {
                    if (!flag) {
                        int diff = map[x][y] -(map[rc[0]][rc[1]] - 1);
                        if (diff <=K) {
                            rc[0] = x;
                            map[x][y] -=diff;
                            v[x][y] = true;
                            findLoad(new int[] { x, y }, length + 1, true, v);
                            map[x][y] += diff;
                            v[x][y] = false;
                        }
                    }
                }
            }
        }
        ans = Math.max(ans, length);
    }
 
    public static boolean isRange(int x, int y) {
        return x >= 0 && y >= 0 && x < N && y < N;
    }
}