1949. [모의 SW 역량테스트] 등산로 조성(JAVA)

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

SW Expert Academy

 

문제설명

 

기본적인 DFS문제지만 공사 할 수 있는 것을 잘 유의하며 접근해야한다.

 

알고리즘

 

1. DFS로 가장 높은 봉우리부터 4방향 탐색을 시작한다.

 

2. 만약 다음 갈 수 있는 봉우리 - 현재 높이 가 공사할 수 있는 높이보다 작아야 공사가 가능하다.

 

3. 2번의 경우 공사 한 것을 체크 한뒤 DFS를 진행한다.

 

주의사항

1. 나 같은 경우 시작 할 때 봉우리를 체크 안해줘서 46개의 TK을 맞았었다.

 

2. 공사 한 후 공사된 높이를 map에 저장해야한다. 물론 탐색이 끝난 후 다시 원래대로 돌려놔야한다.

-> DFS이기에 가능한 코드

 

구현

 

package algorithm;
import java.util.Arrays;
import java.util.LinkedList;
///////////////////////////////////////////////////////////////////
import java.util.Scanner;
import java.util.StringTokenizer;


import java.io.BufferedOutputStream;
import java.io.BufferedReader;
//import java.io.BufferedOutputStream;
import java.io.FileInputStream;
import java.io.InputStreamReader;

class Solution_등산로
{
    static int N;
    static int K;
    static int map[][];
    static int dir[][]= {{-1,0},{1,0},{0,-1},{0,1}};
    static int cha;
    static int max_c;
    static boolean check;
    static boolean che[][];
    public static void main(String args[]) throws Exception
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine().trim());
        for (int test_case = 1; test_case <= T; test_case++) 
        {
            StringTokenizer s = new StringTokenizer(in.readLine()," ");
            N = Integer.parseInt(s.nextToken());
            K = Integer.parseInt(s.nextToken());
            map = new int[N][N];
            che = new boolean[N][N];
            int max =0;
            for (int i = 0; i < N; i++) {
                s=  new StringTokenizer(in.readLine()," ");
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(s.nextToken());
                    if(map[i][j] > max)
                    {
                        max = map[i][j];
                    }
                }
            }
            max_c=0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(max == map[i][j])
                    {
                        che[i][j] = true;
                        cha = 0;
                        DFS(i,j,0);
                        che[i][j] = false;
                    }
                }
            }
            System.out.println("#"+test_case+" "+(max_c+1));
        }
    }
    private static void DFS(int y, int x,int cnt) {
        //System.out.println("y= "+y+" x="+x+" cnt= "+cnt);
        if(cnt > max_c)
            max_c = cnt;
        for (int i = 0; i < 4; i++) {
            int ny = y+dir[i][0];
            int nx = x+dir[i][1];
            if(ny > -1 && nx > -1 && ny < N && nx<N)
            { 
                if(map[ny][nx] <map[y][x] && !che[ny][nx])
                {
                    che[ny][nx] = true;
                    DFS(ny,nx,cnt+1);
                    che[ny][nx] = false;

                }
                else if(!check && map[ny][nx] -map[y][x] < K && !che[ny][nx]) //공사 할수 있을 정도 높이면
                {
                    check = true;
                    che[ny][nx] = true;
                    cha = map[ny][nx];
                    map[ny][nx] = map[y][x]-1;
                    DFS(ny,nx,cnt+1);
                    map[ny][nx] = cha;
                    check = false;
                    che[ny][nx] = false;
                }
            }
        }//end for
    }
}