[알고리즘/JAVA] SWEA 1949 등산로 조성 (BFS,DFS)

모의 SW 역량테스트를 준비하면서 등산로 조성이라는 문제를 접하게 되었다..

문제 링크는 

SW Expert Academy

와 같다. 

---

초기 해결 방안

-> 처음 이 문제를 읽고 BFS로 풀어야겠다는 생각을 했다. 그 이유는 아직 DFS는 익숙하지 않고, BFS의 문제를 많이 접해봤기 때문이다. 

    이 문제는 BFS + 완전 탐색이라고 생각하였고 문제를 풀었다.

코드 (BFS + 완전탐색)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Solution {
    static int[][] search = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
    static int N, K, MAX = Integer.MIN_VALUE;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            MAX = Integer.MIN_VALUE;
            StringTokenizer token = new StringTokenizer(br.readLine());
            N = Integer.parseInt(token.nextToken());
            K = Integer.parseInt(token.nextToken());
            int[][] arr = new int[N][N];
            int max = 0;
            for (int r = 0; r < N; r++) {
                token = new StringTokenizer(br.readLine());
                for (int c = 0; c < N; c++) {
                    arr[r][c] = Integer.parseInt(token.nextToken());
                    if (max < arr[r][c]) {
                        max = arr[r][c];
                    }
                }
            }
            List<Point> list = new ArrayList<>();
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    if (max == arr[r][c]) {
                        list.add(new Point(r, c));
                    }
                }
            }
 
            for (int k = 0; k <= K; k++) {
                for (int r = 0; r < N; r++) {
                    for (int c = 0; c < N; c++) {
                        if (arr[r][c] - k < 0) {
                            continue;
                        } else {
                            arr[r][c] -= k;
                        }
                        for (int i = 0; i < list.size(); i++) {
                            bfsQueue(list.get(i).r, list.get(i).c, arr);
                        }
                        arr[r][c] += k;
                    }
                }
            }
            System.out.println("#" + tc + " " + MAX);
        }
    }
 
    static void bfsQueue(int r, int c, int[][] copy) {
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(r, c));
        int time = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            time++;
            for (int i = 0; i < size; i++) {
                Point top = queue.poll();
                for (int s = 0; s < search.length; s++) {
                    int nr = top.r + search[s][0];
                    int nc = top.c + search[s][1];
                    if (isIn(nr, nc)  && copy[top.r][top.c] > copy[nr][nc]) {
                        queue.offer(new Point(nr, nc));
                    }
                }
            }
        }
        if (MAX < time) {
            MAX = time;
        }
    }
 
    static boolean isIn(int r, int c) {
        return r >= 0 && c >= 0 && r < N && c < N;
    }
 
    static class Point {
        int r, c;
 
        public Point(int r, int c) {
            super();
            this.r = r;
            this.c = c;
        }
 
        @Override
        public String toString() {
            return "Point [r=" + r + ", c=" + c + "]";
        }
    }
}

코드 설명

1. 높은 봉우리에서 시작한다고 했으니까 리스트를 만들어서 높은 봉우리의 점들을 추가해주었다.
2. 한 곳을 정해서 최대 깊이 K까지 지형을 깎을 수 있다고 했으니까 모든 점에서 0부터 K까지 깎는 완전 탐색을 한다. 그 안 로직에서 BFS를 실행시켜준다.
3. BFS는 방문처리를 하지 않고, 배열 범위를 벗어나지 않고, 지형이 낮아지는 쪽이면 깊이 탐색을 실행시켰다. 그리고 size를 통해 실행 횟수를 조절해주었다. 한번 실행할 때마다 time을 늘려주고, time의 최댓값을 답으로 출력하였다.

결과

메모리가 생각보다 많이 나왔다.

 

결과 피드백

BFS를 통해 되는 점들을 모두 Queue에 집어넣다 보니 메모리가 많이 나온 듯하다. 

그래서 이번에는 DFS를 이용해서 이문제를 풀어보려고 하였다.

수정 코드 (DFS + 완전 탐색)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Solution {
    static int[][] search = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
    static int N, K, MAX = Integer.MIN_VALUE;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            MAX = Integer.MIN_VALUE;
            StringTokenizer token = new StringTokenizer(br.readLine());
            N = Integer.parseInt(token.nextToken());
            K = Integer.parseInt(token.nextToken());
            int[][] arr = new int[N][N];
            int max = 0;
            for (int r = 0; r < N; r++) {
                token = new StringTokenizer(br.readLine());
                for (int c = 0; c < N; c++) {
                    arr[r][c] = Integer.parseInt(token.nextToken());
                    if (max < arr[r][c]) {
                        max = arr[r][c];
                    }
                }
            }
            List<Point> list = new ArrayList<>();
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    if (max == arr[r][c]) {
                        list.add(new Point(r, c));
                    }
                }
            }
 
            for (int k = 0; k <= K; k++) {
                for (int r = 0; r < N; r++) {
                    for (int c = 0; c < N; c++) {
                        if (arr[r][c] - k < 0) {
                            continue;
                        } else {
                            arr[r][c] -= k;
                        }
                        for (int i = 0; i < list.size(); i++) {
                            dfs(list.get(i).r, list.get(i).c, 1, arr);
                        }
                        arr[r][c] += k;
                    }
                }
            }
            System.out.println("#" + tc + " " + MAX);
        }
    }
 
    static void dfs(int r, int c, int cnt, int[][] copy) {
        for (int s = 0; s < search.length; s++) {
            int nr = r + search[s][0];
            int nc = c + search[s][1];
            if (isIn(nr, nc) && copy[r][c] > copy[nr][nc]) {
                dfs(nr, nc, cnt + 1, copy);
            }
        }
        if (MAX < cnt) {
            MAX = cnt;
        }
    }
 
    static boolean isIn(int r, int c) {
        return r >= 0 && c >= 0 && r < N && c < N;
    }
 
    static class Point {
        int r, c;
 
        public Point(int r, int c) {
            super();
            this.r = r;
            this.c = c;
        }
    }
}

 

코드 변경 사항

-> DFS를 재귀로 구현하여 cnt값을 늘려주었다. 조건에 만족하게 된다면 계속해서 cnt값을 늘려주었고, cnt값 중 최댓값을 값으로 출력하였다.

 

결과

메모리와 시간이 줄었다.

---

결론

위 문제는 DFS or BFS와 백트래킹을 이용해서 푸는 문제였다. 하나만 깎는 조건이 까다롭기 때문에 완전 탐색을 통해 푸는 것이 해답이다.