[SWEA] 1949. 등산로 조성

이차원 행렬상에서 특정조건의 최장길이를 구하는 문제이다.

최장길이를 구하는 문제는 DFS와 백트래킹으로 풀면 쉽게 풀 수 있다. 맨처음 이문제를 접근하였을 때 BFS와 3차원 visit배열로 접근하였다. 이 방법으로도 풀리긴 하지만 DFS와 2차원 visit 배열의 백트래킹을 사용하면 훨씬 간결한 코드를 얻을 수 있다.

이 문제에선 주의할점이 두가지 있는데, 첫째 산을 깎을수 있다는 점과 둘째 깎을때 꼭 K만큼이 아니라 K이하 만큼 깎을수 있다는 점이다. 두가지를 유념하여 DFS를 한다면 쉽게 풀수 있었던 문제이다.

package swea;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
import javax.print.attribute.standard.Media;
 
 
public class Solution_1949_등산로조성 {
 
    static int[] di= {-1,0,1,0};
    static int[] dj= {0,1,0,-1};
    
    static int N,K;
    static int[][] map;
    static boolean[][] visit;
    
    static int answer;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int T=Integer.parseInt(br.readLine());
        
        for(int tc=1;tc<=T;tc++) {
            st=new StringTokenizer(br.readLine());
            N=Integer.parseInt(st.nextToken());
            K=Integer.parseInt(st.nextToken());
            
            int max=0;
            map=new int[N][N];
            for(int i=0;i<N;i++) {
                st=new StringTokenizer(br.readLine());
                for(int j=0;j<N;j++) {
                    int num=Integer.parseInt(st.nextToken());
                    map[i][j]=num;
                    max=Integer.max(max,num);
                }
            }
 
            visit=new boolean[N][N];
            answer=0;
            for(int i=0;i<N;i++) {
                for(int j=0;j<N;j++) {
                    if(map[i][j]==max) {
                        visit[i][j]=true;
                        dfs(i,j,1,map[i][j],false);
                        visit[i][j]=false;
                    }
                }
            }
            System.out.println("#"+tc+" "+answer);
            
        }
    }
    
    static void dfs(int i,int j,int count,int value,boolean kUsed) {
        answer=Math.max(answer, count);
        
        for(int dir=0;dir<4;dir++) {
            int nextI=i+di[dir];
            int nextJ=j+dj[dir];
            
            if(nextI<0||nextI>=N ||nextJ<0 ||nextJ>=N)
                continue;
            
            if(kUsed==false) {
                if(value>map[nextI][nextJ] && visit[nextI][nextJ]==false) {
                    visit[nextI][nextJ]=true;
                    dfs(nextI, nextJ, count+1, map[nextI][nextJ], false);
                    visit[nextI][nextJ]=false;
                }else if(value<=map[nextI][nextJ] && visit[nextI][nextJ]==false) {
                    int minus=0;
                    for(int index=1;index<=K;index++) {
                        if(value>map[nextI][nextJ]-index) {
                            minus=index;break;
                        }
                    }
                    if(minus!=0) {
                        visit[nextI][nextJ]=true;
                        dfs(nextI, nextJ, count+1, map[nextI][nextJ]-minus, true);
                        visit[nextI][nextJ]=false;
                    }
                }
                
                
            }else if(kUsed==true) {
                if(value>map[nextI][nextJ] && visit[nextI][nextJ]==false) {
                    visit[nextI][nextJ]=true;
                    dfs(nextI,nextJ,count+1,map[nextI][nextJ],true);
                    visit[nextI][nextJ]=false;
                }
            }
        }
        
    }
}