[Algorithm] SWEA_등산로 조성_1949 (JAVA)

📝문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq&categoryId=AV5PoOKKAPIDFAUq&categoryType=CODE&problemTitle=1949&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

---

💡풀이

문제 유형

완전탐색

 

걸린 시간

75분

 

시간 복잡도

O(TxN^2x4^D)

 

풀이 방법 도출

 

구해야 할 문제:

가장 높은 봉우리부터 낮아지는 봉우리의 최대 길이를 구한다.

 

접근 방법:

가장 높은 봉우리를 구한다. (max)

봉우리 중 max와 일치할 때 dfs를 돌린다. (첫번째 방문 지점을 방문 처리하는 것을 잊지 말자! 46/51개 통과 이유여씀..)

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        if (arr[i][j] == max) {
            visited = new boolean[N][N];
            visited[i][j] = true;
            cnt = 0;
            dfs(i, j, 1);
            visited[i][j] = false;
        }
    }
}

 

다음 봉우리가 현재 봉우리보다 작다면 len+1을 해주고 재귀dfs를 호출한다.

if (arr[nx][ny] < arr[x][y]) {
    visited[nx][ny] = true;
    dfs(nx, ny, len + 1);
    visited[nx][ny] = false;
}

 

다음 봉우리가 현재 봉우리보다 크거나 같다면 1부터 K까지 다음 봉우리의 지형을 깎는다.

이때, 깎은 봉우리의 높이가 0보다 작아지는 순간 반복문을 탈출한다.

깎은 봉우리의 높이가 현재 봉우리보다 작다면 전역변수로 선언한 깎은 횟수 cnt=1로 바꿔주고 기존 배열값도 깎은 만큼 빼준다.

dfs 호출 후 백트래킹을 위해 기존 설정들을 돌려놓는다.

else if (cnt == 0) {
    for (int j = 1; j <= K; j++) {
        if (arr[nx][ny] - j < 0) {
            break;
        }
        if (arr[nx][ny] - j < arr[x][y]) {
            visited[nx][ny] = true;
            cnt = 1;
            arr[nx][ny] -= j;
            dfs(nx, ny, len + 1);
            visited[nx][ny] = false;
            cnt = 0;
            arr[nx][ny] += j;
        }
    }

}

 

전체코드

import java.util.*;
import java.io.*;
 
class Solution {
    static int cnt;
    static int answer;
    static int[][] arr;
    static int N, K;
    static boolean[][] visited;
    static int[] dx = new int[]{0, 1, 0, -1};
    static int[] dy = new int[]{1, 0, -1, 0};
 
    public static void main(String[] args) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int T = Integer.parseInt(br.readLine());
 
        StringBuilder sb = new StringBuilder();
 
        for (int t = 1; t <= T; t++) {
            answer = 0;
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
 
            arr = new int[N][N];
 
            int max = 0;
 
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                    max = Math.max(arr[i][j], max);
                }
            }
 
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (arr[i][j] == max) {
                        visited = new boolean[N][N];
                        visited[i][j] = true;
                        cnt = 0;
                        dfs(i, j, 1);
                        visited[i][j] = false;
                    }
                }
            }
            sb.append("#").append(t).append(" ").append(answer).append("\n");
        }
 
        System.out.println(sb);
    }
 
    public static void dfs(int x, int y, int len) {
        answer = Math.max(answer, len);
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                if (!visited[nx][ny]) {
                    if (arr[nx][ny] < arr[x][y]) {
                        visited[nx][ny] = true;
                        dfs(nx, ny, len + 1);
                        visited[nx][ny] = false;
                    } else if (cnt == 0) {
                        for (int j = 1; j <= K; j++) {
                           if (arr[nx][ny] - j < 0) {
                                break;
                            }
                            if (arr[nx][ny] - j < arr[x][y]) {
                                visited[nx][ny] = true;
                                cnt = 1;
                                arr[nx][ny] -= j;
                                dfs(nx, ny, len + 1);
                                visited[nx][ny] = false;
                                cnt = 0;
                                arr[nx][ny] += j;
                            }
                        }
                    }
                }
            }
        }
    }
}

---

🤔Review

삼성역량테스트 문제답게 삼성스러운 문제였다 ^0^