[SWEA] 1949 등산로조성

문제보기

처음에는 뭣모르고 bfs로 하려고 했으나, 경사로를 깎을때 / 안깎을때 맵이 변경되는 부분을 어떻게 처리해야할지 감이 안와서 그냥 재귀로 풀었다. 변경되는 맵은 그때마다 인자로 넘겨주면서…

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

  static int[] dx = {1, -1, 0, 0};
  static int[] dy = {0, 0, 1 ,-1};
  static int n;
  static int k;
  static int max;

  static void go(int x, int y, int drill, int len, int[][] map, boolean[][] check) {
		
    // 더이상 진행할 방향이 있는지 여부를 저장 
    boolean end = true;
    // 상하좌우 네 방향 체크
    for(int kk = 0 ; kk < 4 ; kk++) {
      int nx = x + dx[kk];
      int ny = y + dy[kk];

      // 맵 내에 존재하는 좌표 && 방문한적 없음
      if(nx >= 0 && nx < n && ny >= 0 && ny < n && check[nx][ny] == false) {
        // 현재 지점보다 낮다면 
        if(map[nx][ny] < map[x][y]) {
          check[nx][ny] = true; // 방문 체크
          end = false; // 진행할 방향이 적어도 하나 있다
          go(nx, ny, drill, len+1, map, check);
          check[nx][ny] = false;
          
        }else if(drill == 0 && map[nx][ny] - map[x][y] < k) { // 만약 현재 지점보다 높거나 같지만
          // 아직 드릴을 한번도 안썼고
          // 해당 지점이 최대 드릴가능 깊이로 충분히 커버된다면
        
          check[nx][ny] = true;
          end = false;
          int save = map[nx][ny];
          map[nx][ny] = map[x][y]-1; // 현재지점보다 딱 1만큼만 낮게 깍아준다
          go(nx, ny, 1, len+1, map, check); // drill 인자가 1로 변경되어 재귀 호출
          map[nx][ny] = save; // 변경 전의 맵으로 바꿔주기(for문이 아직 더 돌아야 하므로...)
          check[nx][ny] = false;

        }
      }

    }
    if(end) { // 더이상 네 방향 어디로도 갈 수 없다면 종료
      if( len > max ) max = len;
      return;
    }

  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int t = Integer.parseInt(br.readLine());
    int idx = 1;
    while(t-->0) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      n = Integer.parseInt(st.nextToken());
      k = Integer.parseInt(st.nextToken());

      int[][] map = new int[n][n];
      // 정상 지점 저장
      int peek = 0;
      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());
          if(map[i][j] > peek) peek = map[i][j];
        }
      }
      max = 0;

      for(int i = 0 ; i < n ; i++) {
        for(int j = 0 ; j < n ; j++) {
          if(map[i][j] == peek) {
            boolean[][] check = new boolean[n][n];
            check[i][j] = true;
            go(i, j, 0, 1, map, check);
          }
        }
      }
      System.out.println("#" + idx++ + " " + max);
    }
  }
}