[SWEA] 모의 SW 역량 테스트 :: 1949번 등산로 조성 (dfs, 백트래킹)

sw expert academy 1949 등산로 조성 자바(java) 풀이

• 모의 SW 역량 테스트
• sw expert academy 1949 등산로 조성
  
  
  

문제정리

1. 등산로를 만들기 위한 부지는 NxN 크기이다.
2. 등산로는 가장 높은 봉우리에서 시작된다.
3. 등산로는 높은 지형에서 낮은 지형으로 가로 or 세로 방향으로 연결되어 있어야 한다.
4. 높이가 같은 곳, 대각선 연결은 불가하다.
5. 딱 한 곳을 정해서 최대 k 깊이 만큼 깎는 공사를 할 수 있다. (정수 단위로만 깎을 수 있으며 1보다 작게 만들 수도 있다.)
   이때 k 깊이 만큼 깎아서 가장 높은 곳이 변하더라고 봉우리는 초기 봉우리를 이용한다.

• 가장 긴 등산로를 찾아 등산로의 길이를 출력해라!
  
  
  

문제풀이

1. 가장 높은 봉우리를 구합니다.
2. 1~k까지 map의 좌상단 부터 우하단까지 차례대로 빼 나갑니다.
   한 위치에서 k만큼 빼서 깎고 모든 봉우리에서 각각 dfs를 순회하며 등산로의 길이를 구해나갑니다.
   이떄 dfs를 순회하기전에 최초의 위치를 방문처리 해줍니다.
3. 뺀 위치에 다시 뺀 값을 더해주어 높이를 원상복귀 시킵니다.
4. 그리고 어느 부지도 깎지 않았을 경우 dfs를 순회하여 등산로의 길이를 구하여 최대 등산로의 길이를 갱신시킵니다.
   
   
   

dfs

1. 위, 아래, 왼쪽, 오른쪽 4 방향으로 이동합니다.
   이동하려는 위치가 유효하고 방문하지 않았을 경우,
   현 위치보다 더 작은 높이를 갖는 경우만 방문합니다.
2. 방문시 길이를 1 증가시켜 인자로 넘겨줍니다.
3. 4가지 방향으로 탐색이 모두 끝났을 경우 길이가 max보다 크면 갱신해줍니다.
   
   
   

등산로 조성 자바 코드

좀더 자세한 내용은 주석에 달아 두었습니다!!

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.io.IOException;
import java.util.Stack;

class Pos {
    int x;
    int y;

    Pos(int x, int y){
        this.x = x;
        this.y = y;
    }
}

class Solution {
    static int N, K;
    static int[][] map;
    static int max;
    static ArrayList<Pos> maxHeightPos;
    // 위,아래, 왼쪽, 오른쪽
    static int[] xdir = {-1,1,0,0};
    static int[] ydir = {0,0,-1,1};
    static boolean[][] visited;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testNum = Integer.parseInt(br.readLine());

        for(int test=1; test<=testNum; test++){
            // N과 K 입력받기
            String[] temp = br.readLine().split(" ");
            N = Integer.parseInt(temp[0]);
            K = Integer.parseInt(temp[1]);
            map = new int[N][N];

            // 부지 중 최대 높이
            int maxHeight = 0;

            // 부지 입력받기
            for(int i=0; i<N; i++){
                temp = br.readLine().split(" ");
                for(int j=0; j<N; j++){
                    int t = Integer.parseInt(temp[j]);
                    maxHeight = maxHeight < t ? t : maxHeight;
                    map[i][j] = t;
                }
            }

            maxHeightPos = new ArrayList<>();
            findMaxHeightPos(maxHeight);
            max = 0;
            // 최대 k까지 뺀다
            for(int k=1; k<=K; k++){
                // map의 모든 위치를 빼나간다.
                for(int i=0; i<N; i++){
                    for(int j=0; j<N; j++){
                        map[i][j] -= k;
                        // 모든 봉우리에서 dfs
                        for(int w=0; w<maxHeightPos.size(); w++){
                            Pos p = maxHeightPos.get(w);
                            visited = new boolean[N][N];
                            visited[p.x][p.y] = true;
                            dfs(p.x, p.y, 1);
                        }
                        // 원상 복구
                        map[i][j] += k;
                    }
                }
            }

            // 부지를 깎지 않았을 경우 dfs
            for(int i=0; i<maxHeightPos.size(); i++){
                Pos p = maxHeightPos.get(i);
                visited = new boolean[N][N];
                visited[p.x][p.y] = true;
                dfs(p.x, p.y, 1);
            }

            System.out.println("#" + test + " " + max);
        }
        br.close();
    }

    public static void dfs(int x, int y, int len){
        for(int i=0; i<4; i++){
            int dx = x + xdir[i];
            int dy = y + ydir[i];
            // 유요한 위치이고 방문하지 않았을 경우
            if(isValidPosition(dx, dy) && !visited[dx][dy]){
                // 더 작은 부지 일 경우 방문
                if(map[x][y] > map[dx][dy]){
                    visited[dx][dy] = true;
                    dfs(dx, dy, len+1);
                    visited[dx][dy] = false;
                }
            }
        }
        max = max < len ? len : max;
    }

    public static void findMaxHeightPos(int maxHeight){
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(map[i][j] == maxHeight)
                    maxHeightPos.add(new Pos(i, j));
            }
        }
    }

    public static boolean isValidPosition(int x, int y){
        if(x < 0 || x >= N || y < 0 || y >= N) return false;
        return true;
    }
}