SWEA ) 등산로 조성

---

문제 ↓

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

---

등산로를 개척하면서 단 한 경로의 높이를 낮추어서

 

최장거리의 경로를 구하는 문제이다.

 

이경우 N이 충분히 작기때문에 DFS로 해결이 가능했지만,

 

N이 크다면 BFS + 백트래킹 + VISIT배열변경 등의 

 

다양한 방법으로 접근해야 했었던 문제이다.

 

 

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

비슷한 문제 같지만, 위문제를 DFS로 제출했더니 바로 시간초과가 났다..

 

---

문제에 접근방법은 DFS를 통한 경로를 탐색하면서 자기보다 큰 값을 만났을때 ( K ) 0부터 K까지의

 

값을 빼보면서 경로를 진행하는 것이다. 

 

그리고 맵을 변경했다는 BOOLEAN변수로 경로에서 단 한번만 변경이 가능하게 하면서 탐색한다.

 

전체 탐색이 완료되면 가장 긴 경로를 답으로 선택한다.

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;
 
public class Solution {
    static int T,N,K,cnt=0, h_max, res,answer;
    static int map[][];
    static boolean visit[][];
    static int heightest_pos[][];
    static int dx[] = {0,0,-1,1};
    static int dy[] = {-1,1,0,0};
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     
    public static void input() throws Exception {
         
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken())+1;
        K = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        visit = new boolean[N][N];
         
        h_max = -1;
         
        for (int y = 1 ; y <N ; y++) {
            st = new StringTokenizer(br.readLine());
            for(int x = 1 ;x <N ; x++) {
                map[y][x] = Integer.parseInt(st.nextToken());
                h_max = Math.max(h_max, map[y][x]);
            }
        }
         
        heightest_pos = new int[5][2];
         
        for(int y= 1; y < N ; y++){
            for(int x=1; x< N; x++){
                if(map[y][x]== h_max){
                    heightest_pos[cnt][0] = y; // 0 은 y
                    heightest_pos[cnt][1] = x; // 1 은 x
                    cnt++;
                }
            }
        }
    }
     
    public static void DFS(int y, int x ,boolean breakor, int len , int now_h) {
         
        res = Math.max(res, len);
         
        for(int index = 0 ; index < 4 ; index++) {
             
            int nx = x + dx[index];
            int ny = y + dy[index];
             
            if(nx >=1 && ny >=1 && nx < N && ny < N) {
                 
                if(map[ny][nx] < now_h && !visit[ny][nx]){
                     
                    visit[ny][nx] = true;
                    DFS(ny,nx,breakor,len+1 , map[ny][nx]);
                    visit[ny][nx] = false;
                }
                else if((map[ny][nx] - K < now_h) && !breakor && !visit[ny][nx]) {
                     
                    for(int hh =1 ; hh <=K ; hh++) {
                         
                        if(map[ny][nx] - hh < now_h){
                             
                            breakor= true;
                            visit[ny][nx] = true;
                            DFS(ny,nx,breakor,len+1, map[ny][nx] -hh);
                            visit[ny][nx] = false;
                            breakor =false;
                        }
                    }
                }
            }
        }
    }
     
    public static void main(String[] args) throws Exception{
        T = Integer.parseInt(br.readLine().trim());
        for(int tc =1 ; tc<=T ;tc++) {
            input();
            for(int index=0; index< cnt; index++) {
                int y = heightest_pos[index][0];
                int x = heightest_pos[index][1];
                visit[y][x] = true;
                DFS( y, x, false,1, h_max);
                visit[y][x] = false;
                answer = Math.max(answer, res);
            }
         
            System.out.println("#"+tc+" "+answer);
            answer =0; res =0; cnt =0;
        }
    }
 
     
}

---