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

---

 

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

 

 

---

 

 

 

문제 링크

 

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

 

 

 

---

 

 

 

배열 한 변의 길이가 8인거 보고, 바로 완탐으로 풀기로 했다.

봉우리를 0~K까지 깎으면서 배열을 다 돌았다.

 

스터디 코드 리뷰를 하며 DFS로 굉장히 신박하게 푼 코드를 봤고, DFS로 다시 풀어보았다.

 

DFS로 탐색하는 방법은 크게 두가지였다.

1) 그냥 갈 수 있는 경우 ( 현재 봉우리 > 다음 봉우리 )

2) 깎으면 갈 수 있는 곳 ( 깎은 적이 없고, 현재 봉우리 > 다음 봉우리 - K )

 

매개변수로 (위치, 현재까지 길이, 깎은 적 있는 지 없는 지 여부) 를 넘겨주면서 DFS로 돌렸다.

 

▼ 무식하게 푼 코드

package com.study.samsung;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
 
public class Solution_sw_1949_등산로조성 {
 
    static int T, N, K, answer;
    static int[][] map;
    static ArrayList<Point> tops;
    static boolean[][] isVisited;
    static int[] dx = { 0, 1, 0, -1 };
    static int[] dy = { -1, 0, 1, 0 };
 
    static class Point {
        int y;
        int x;
 
        Point(int y, int x) {
            this.y = y;
            this.x = x;
        }
 
        @Override
        public String toString() {
            return "Point [y=" + y + ", x=" + x + "]";
        }
 
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            String[] str = br.readLine().split(" ");
            N = Integer.parseInt(str[0]); // N : 한 변의 길이
            K = Integer.parseInt(str[1]); // K : 최대 공사 가능 깊이
            map = new int[N][N];
            isVisited = new boolean[N][N];
            tops = new ArrayList<Point>();
            int highest = Integer.MIN_VALUE;
            for (int i = 0; i < N; i++) {
                str = br.readLine().split(" ");
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(str[j]);
                    highest = Math.max(highest, map[i][j]); // 가장 높은 봉우리 찾기
                }
            }
 
            // 가장 높은 봉우리들 찾아서 queue에 넣기
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (map[i][j] == highest) {
                        tops.add(new Point(i, j));
                    }
                }
            }
 
            answer = 0;
            // 0~K로 봉우리 하나하나 깎아보기
            for (int k = 0; k <= K; k++) {
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < N; j++) {
                        if (map[i][j] - k < 0)
                            continue;
                        map[i][j] -= k;
                        for (Point top : tops) {
                            dfs(top, 1);
                        }
                        map[i][j] += k;
                    }
                }
            }
 
            sb.append("#" + t + " " + answer + "\n");
        } // test case
        System.out.println(sb.toString());
    } // main
 
    static void dfs(Point point, int length) {
        if (isVisited[point.y][point.x])
            return;
        else {
            answer = Math.max(answer, length);
            for (int d = 0; d < 4; d++) {
                int ny = point.y + dy[d];
                int nx = point.x + dx[d];
                if (isRange(ny, nx) && !isVisited[ny][nx] && map[point.y][point.x] > map[ny][nx]) {
                    // 배열범위 안 && 방문X && 현재보다 낮은 곳
                    isVisited[point.y][point.x] = true;
                    dfs(new Point(ny, nx), length + 1);
                    isVisited[point.y][point.x] = false;
                }
            }
        }
    }
 
    private static boolean isRange(int ny, int nx) {
        return ny >= 0 && nx >= 0 && ny < N && nx < N;
    }
 
}
 

 

package com.study.samsung;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
 
public class Solution_sw_1949_등산로조성2 {
 
    static int T, N, K, answer;
    static int[][] map;
    static ArrayList<Point> tops;
    static boolean[][] isVisited;
    static int[] dx = { 0, 1, 0, -1 };
    static int[] dy = { -1, 0, 1, 0 };
 
    static class Point {
        int y;
        int x;
 
        Point(int y, int x) {
            this.y = y;
            this.x = x;
        }
 
        @Override
        public String toString() {
            return "Point [y=" + y + ", x=" + x + "]";
        }
 
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            String[] str = br.readLine().split(" ");
            N = Integer.parseInt(str[0]); // N : 한 변의 길이
            K = Integer.parseInt(str[1]); // K : 최대 공사 가능 깊이
            map = new int[N][N];
            isVisited = new boolean[N][N];
            tops = new ArrayList<Point>();
            
            // 가장 높은 봉우리 찾기
            int highest = Integer.MIN_VALUE;
            for (int i = 0; i < N; i++) {
                str = br.readLine().split(" ");
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(str[j]);
                    highest = Math.max(highest, map[i][j]); 
                }
            }
 
            // 가장 높은 봉우리들 찾아서 list에 넣기
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (map[i][j] == highest) {
                        tops.add(new Point(i, j));
                    }
                }
            }
 
            answer = 0;
            for (Point top : tops) {
                isVisited[top.y][top.x] = true;
                dfs(top, 1, false);
                isVisited[top.y][top.x] = false;
            }
 
            sb.append("#" + t + " " + answer + "\n");
        } // test case
        System.out.println(sb.toString());
    } // main
 
    static void dfs(Point point, int length, boolean isDigged) {
        answer = Math.max(answer, length);
        for (int d = 0; d < 4; d++) {
            int ny = point.y + dy[d];
            int nx = point.x + dx[d];
 
            // 배열범위 안 && d방문하지 않은 곳
            if (isRange(ny, nx) && !isVisited[ny][nx]) {
 
                // 낮아서 그냥 갈 수 있는 곳
                if (map[point.y][point.x] > map[ny][nx]) {
                    isVisited[ny][nx] = true;
                    dfs(new Point(ny, nx), length + 1, isDigged);
                    isVisited[ny][nx] = false;
                }
 
                // 높은데 깎으면 갈 수 있는 곳
                else if (!isDigged && map[point.y][point.x] > map[ny][nx] - K) {
                    int origin = map[ny][nx];
                    map[ny][nx] = map[point.y][point.x] - 1;
                    isVisited[ny][nx] = true;
                    dfs(new Point(ny, nx), length + 1, true);
                    isVisited[ny][nx] = false;
                    map[ny][nx] = origin;
                }
            }
        }
    }
 
    private static boolean isRange(int ny, int nx) {
        return ny >= 0 && nx >= 0 && ny < N && nx < N;
    }
 
}