SWEA 모의 1949 등산로 조성

SWEA 모의 1949 등산로 조성

 

 

문제링크

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

SW Expert Academy

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://youtu.be/iQUvCRKKJ6s

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package se.code.모의;

import java.io.BufferedReader;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.StringTokenizer;

/**
 * @author itsmeyjc
 * @since 2020. 5. 1.
 * @see https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq&categoryId=AV5PoOKKAPIDFAUq&categoryType=CODE
 * @mem 23,844
 * @time 111 ms
 * @caution #dfs
 * 공사 쿠폰을 사용했는지 여부에 따라 새로운 분기가 발생한다. 원복시키는거 잊지 말기
 */
public class SWEA_모의_1949_등산로조성 {
    static StringBuilder sb = new StringBuilder();
    static int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    static int TC, N, K;
    static int[][] map;
    static boolean[][] visited;

    static int maxHeight, longestPath;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new StringReader(src));

        TC = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= TC; tc++) {
            // 각 테케별 초기화 항목
            StringTokenizer tokens = new StringTokenizer(br.readLine());
            N = Integer.parseInt(tokens.nextToken()); // 지도의 한 변의 길이 N은 3 이상 8 이하의 정수이다. (3 ≤ N ≤ 8)
            K = Integer.parseInt(tokens.nextToken()); // 최대 공사 가능 깊이 K는 1 이상 5 이하의 정수이다. (1 ≤ K ≤ 5)

            map = new int[N][N];
            visited = new boolean[N][N];

            maxHeight = Integer.MIN_VALUE; // 그 회차의 최대 높이
            for (int r = 0; r < N; r++) {
                tokens = new StringTokenizer(br.readLine());
                for (int c = 0; c < N; c++) {
                    map[r][c] = Integer.parseInt(tokens.nextToken());
                    maxHeight = Math.max(maxHeight, map[r][c]);
                }
            }
            longestPath = 0; // 그 회차의 최대 경로 길이

            // 가장 높은 지점에서 dfs 탐색
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    if (map[r][c] == maxHeight) {
                        dfs(r, c, 1, false);
                    }
                }
            }
            sb.append("#").append(tc).append(" ").append(longestPath).append("\n");
        } // 단위 테스트 케이스
        System.out.println(sb);
    }

    static void dfs(int row, int col, int pathLength, boolean used) {
        // 최대 길이 갱신
        longestPath = Math.max(pathLength, longestPath);
        visited[row][col] = true;

        for (int d = 0; d < dirs.length; d++) {
            int nr = row + dirs[d][0];
            int nc = col + dirs[d][1];

            if (isIn(nr, nc) && !visited[nr][nc]) {
                // 원래부터 내리막이면 그냥 가볼 수 있다.
                if (map[nr][nc] < map[row][col]) {
                    dfs(nr, nc, pathLength + 1, used);
                }
                // 아닐 경우 아직 공사 쿠폰을 사용하지 않았고, 공사 깊이만큼의 차이라면 공사하고 가자
                else {
                    if (!used && map[nr][nc] - K < map[row][col]) {
                        // 원래의 값을 살짝 복사해놓았다가
                        int prev = map[nr][nc];
                        map[nr][nc] = map[row][col] - 1;
                        dfs(nr, nc, pathLength + 1, true);
                        // 원복
                        map[nr][nc] = prev;
                    }
                }
            }

        }
        visited[row][col] = false;
    }

    static boolean isIn(int row, int col) {
        return 0 <= row && row < N && 0 <= col && col < N;
    }


    static String src = "10\r\n" +
                        "5 1\r\n" +
                        "9 3 2 3 2\r\n" +
                        "6 3 1 7 5\r\n" +
                        "3 4 8 9 9\r\n" +
                        "2 3 7 7 7\r\n" +
                        "7 6 5 5 8\r\n" +
                        "3 2\r\n" +
                        "1 2 1\r\n" +
                        "2 1 2\r\n" +
                        "1 2 1\r\n" +
                        "5 2\r\n" +
                        "9 3 2 3 2\r\n" +
                        "6 3 1 7 5\r\n" +
                        "3 4 8 9 9\r\n" +
                        "2 3 7 7 7\r\n" +
                        "7 6 5 5 8\r\n" +
                        "4 4\r\n" +
                        "8 3 9 5\r\n" +
                        "4 6 8 5\r\n" +
                        "8 1 5 1\r\n" +
                        "4 9 5 5\r\n" +
                        "4 1\r\n" +
                        "6 6 1 7\r\n" +
                        "3 6 6 1\r\n" +
                        "2 4 2 4\r\n" +
                        "7 1 3 4\r\n" +
                        "5 5\r\n" +
                        "18 18 1 8 18\r\n" +
                        "17 7 2 7 2\r\n" +
                        "17 8 7 4 3\r\n" +
                        "17 9 6 5 16\r\n" +
                        "18 10 17 13 18\r\n" +
                        "6 4\r\n" +
                        "12 3 12 10 2 2\r\n" +
                        "13 7 13 3 11 6\r\n" +
                        "2 2 6 5 13 9\r\n" +
                        "1 12 5 4 10 5\r\n" +
                        "11 10 12 8 2 6\r\n" +
                        "13 13 7 4 11 7\r\n" +
                        "7 3\r\n" +
                        "16 10 14 14 15 14 14\r\n" +
                        "15 7 12 2 6 4 9\r\n" +
                        "10 4 11 4 6 1 1\r\n" +
                        "16 4 1 1 13 9 14\r\n" +
                        "3 12 16 14 8 13 9\r\n" +
                        "3 4 17 15 12 15 1\r\n" +
                        "6 6 13 6 6 17 12\r\n" +
                        "8 5\r\n" +
                        "2 3 4 5 4 3 2 1\r\n" +
                        "3 4 5 6 5 4 3 2\r\n" +
                        "4 5 6 7 6 5 4 3\r\n" +
                        "5 6 7 8 7 6 5 4\r\n" +
                        "6 7 8 9 8 7 6 5\r\n" +
                        "5 6 7 8 7 6 5 4\r\n" +
                        "4 5 6 7 6 5 4 3\r\n" +
                        "3 4 5 6 5 4 3 2\r\n" +
                        "8 2\r\n" +
                        "5 20 15 11 1 17 10 14\r\n" +
                        "1 1 11 16 1 14 7 5\r\n" +
                        "17 2 3 4 5 13 19 20\r\n" +
                        "6 18 5 16 6 7 8 5\r\n" +
                        "10 4 5 4 9 2 10 16\r\n" +
                        "2 7 16 5 8 9 10 11\r\n" +
                        "12 19 18 8 7 11 15 12\r\n" +
                        "1 20 18 17 16 15 14 13\r\n" +
                        "";
}