[SW Expert Academy] 등산로 조성 풀이

1. 문제

https://swexpertacademy.com/main/identity/anonymous/loginPage.do

SW Expert Academy

2. 풀이 Point

• 링크와스타트 (백준 15661)과 굉장히 유사한 문제이다.
• 주요 입력 자료구조
  • peopleCityMap : 도시 별로 인구수가 저장된 Map
  • List<Integer>[] linkList : 도시 별로 연결되어 있는지를 저장한 연결리스트
  • boolean[] visited : 도시를 2개의 구역으로 나누기 위한 배열

1. N개의 구역이 있을 때, A, B 구역으로 나누는 부분
   • visited 배열의 BackTracking을 통해 True : A 구역, False : B구역으로 판단한다.
2. 구역을 나누었다면 A, B 구역이 연결되어 있는지 확인해야한다.
   • A구역을 담은 Queue와 B구역을 담은 Queue를 만들어 각각 구역을 담는다.
   • isConnected() 안에서 각 구역을 담은 큐를 파라미터로 넘겨주어 BFS 함수를 통해 연결되어 있는지 확인한다.
     • 넘겨받은 큐를 이용하여 BFS 함수를 돌려서 연결 지점을 카운트한다.
     • 이 카운트 수와 큐의 사이즈가 같다면 이는 모든 지점이 연결되었다는 것을 의미한다.
   • 두 지역 모두 연결됨이 확인되었다면 각각 큐에서 꺼내어 합을 구해주고 그 둘의 차를 구하여 result를 갱신한다.
     
     
     

3. 소스코드

import javax.swing.plaf.metal.MetalTheme;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Solution {
    static int N, K;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    static int result = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        for (int i = 1; i <= T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

            int maxHeight = 0; // 입력으로 주어지는 높이 값 중 가장 큰 값
            map = new int[N][N];
            for (int j = 0; j < N; j++) {
                st = new StringTokenizer(br.readLine());
                for (int p = 0; p < N; p++) {
                    map[j][p] = Integer.parseInt(st.nextToken());
                    maxHeight = Math.max(map[j][p], maxHeight);  // 가장 높은 높이 값 갱신
                }
            }

            for (int j = 0; j < N; j++) {
                for (int p = 0; p < N; p++) {
                    if (map[j][p] == maxHeight) {
                        visited = new boolean[N][N];
                        visited[j][p] = true;
                        hikingTrailDFS(j, p, true, 1); // 가장 높은 높이에서 DFS 함수 시작
                    }
                }
            }

            bw.write("#" + i + " " + result + "\\n");
            result = 0;
            // 재귀를 2개를 나누어 탄다. 1 -> 안깍고 돌리기, 2- > 깍고 돌리기
        }
        bw.flush();
        bw.close();
        br.close();
    }

    private static void hikingTrailDFS(int x, int y, boolean flag, int sum) {
        for (int i = 0; i < 4; i++) {
            int xf = x + dx[i];
            int yf = y + dy[i];

            if (xf >= 0 && xf < N && yf >= 0 && yf < N && !visited[xf][yf]) {
                if (map[xf][yf] < map[x][y]) {
                    visited[xf][yf] = true;
										// 다음 탐색할 값이 내 값보다 작다면 그대로 내려가면 된다.
                    hikingTrailDFS(xf, yf, flag, sum + 1);
                    visited[xf][yf] = false;
                }

                else {  // 다음 탐색할 값이 내 값보다 크거나 같으므로 1부터 깍을 수 있는 범위까지 깍는다.
                    if (flag) {
                        for (int j = 1; j <= K; j++) {
                            if (map[xf][yf] - j < map[x][y]) {
                                visited[xf][yf] = true;
                                map[xf][yf] -= j;
																
                                hikingTrailDFS(xf, yf, false, sum + 1);

                                map[xf][yf] += j;
                                visited[xf][yf] = false;
                            }
                        }
                    }
                }
            }
        }
        result = Math.max(result, sum);
    }
}

4. 배운점

• DFS를 돌릴 때 static 변수는 위험할 수 있다.
  • 1번 시간선에서 static 변수의 값을 조정한 후 2번 시간선으로 재귀를 탔다면 돌아왔을 때 이를 수정해줘야 하는 번거로움이 생긴다.
  • 이를 잘못하면 잘못된 값으로 결과가 나온다.
  • 재귀를 탈때는 static 변수보다는 파라미터를 이용하자.
    
    
    

5. 점수

85/100