SWEA D5 1798 범준이의 제주도 여행계획

SWEA D5 1798 범준이의 제주도 여행계획

 

 

문제링크

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

SW Expert Academy

 

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

 

동영상 설명

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

https://www.youtube.com/watch?v=I94eNY91MtU

 

 

소스 보기

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

package se.code.d5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

/**
 * @author itsmeyjc
 * @since 2020. 3. 8.
 * @see https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4x9oyaCR8DFAUx&categoryId=AV4x9oyaCR8DFAUx&categoryType=CODE
 * @mem 33,260 kb
 * @time 975 ms
 * @caution #combination 작업 순서 1. 입력 처리 --> 그래프 작성 --> Point class 디자인 --> 지점 정보
 * 등록 --> 단순히 최대 만족도만 구해보고 --> 경로를 stack으로 저장
 */
public class SWEA_D5_1798_범준이의제주도여행계획 {
    static StringBuilder sb = new StringBuilder();

    static int TC;
    static int N, M;


    // 관리할 지점들
    static Point airPort;
    static List<Point> hotels;
    static List<Point> points;
    // 각 지점별 비용 그래프
    static int[][] graph;
    // 최대 만족도
    static int maxSatis;
    // 최대 만족도를 얻는 경로
    static List<Integer> maxSatisPath;
    // 탐색해보는 임시 경로
    static Stack<Integer> tempPath;

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

        for (int t = 1; t <= TC; t++) {
            StringTokenizer tokens = new StringTokenizer(br.readLine());
            N = Integer.parseInt(tokens.nextToken());// 호텔 + 공항 + 관광지, N은 3이상 35이하이다. (3≤ N ≤35)
            M = Integer.parseInt(tokens.nextToken());// 휴가일, 1이상 5이하이다. (1≤ M ≤5)

            // 지점별 비용 그래프 작성 -
            // 입력 받을 때 주의점:
            // 다음 N-1개 줄에는 지점간의 이동 소요시간 정보가 주어지는데,
            // i번째 줄에는 i번째 지점으로부터 i+1~N번 지점까지의 이동 소요시간이 공백으로 구분되어 주어진다.
            // 해당 경로는 반대로 갈 때도 동일한 이동 소요시간을 갖는다.
            graph = new int[N + 1][N + 1];
            for (int r = 1; r < N; r++) {
                tokens = new StringTokenizer(br.readLine());
                for (int c = r + 1; c < graph.length; c++) {
                    graph[r][c] = graph[c][r] = Integer.parseInt(tokens.nextToken());
                }
            }

            /*
            System.out.println("비용 그래프 확인");
            for (int[] row : graph) {
                System.out.println(Arrays.toString(row));
            }
            
            */

            // 지점 정보 가져오기
            points = new ArrayList<>();
            hotels = new ArrayList<>();

            for (int n = 1; n <= N; n++) {
                tokens = new StringTokenizer(br.readLine()); // P 240 6
                String type = tokens.nextToken();
                if (type.equals("H")) {
                    hotels.add(new Point(type, n, 0, 0, null));
                } else if (type.equals("A")) {
                    airPort = new Point(type, n, 0, 0, null);
                } else {
                    points.add(new Point(type, n, Integer.parseInt(tokens.nextToken()),
                            Integer.parseInt(tokens.nextToken()), null));
                }
            }
            /*
              System.out.println(airPort); 
              System.out.println(hotels);
              System.out.println(points); // 입력 완료
             */

            // 지점들의 가장 가까운 호텔 찾아주기 - 그래프에게 호텔과 지점사이의 거리 물어보기
            for (Point p : points) {
                int min = Integer.MAX_VALUE;
                for (Point h : hotels) {
                    if (graph[p.idx][h.idx] < min) {
                        min = graph[p.idx][h.idx];
                        p.nearH = h;
                    }
                }
            }

            maxSatis = Integer.MIN_VALUE;
            tempPath = new Stack<>();

            // 값 구해보기.
            sol(0, airPort, 0, 0, new boolean[N + 1], 0);

            // 결과 출력 - 여전히 만족도가 MIN_VALUE이면 여행 못한 것
            sb.append("#").append(t).append(" ");
            if (maxSatis == Integer.MIN_VALUE) {
                sb.append(0);
            }
            // 나머지 경우에 대해 만족도와 경로 출력하기.
            else {
                sb.append(maxSatis).append(" ");
                for (int i = 0; i < maxSatisPath.size(); i++) {
                    sb.append(maxSatisPath.get(i)).append(" ");
                }
            }
            sb.append("\n");

        }
        System.out.println(sb);
    }

    static void sol(int day, Point start, int satis, int time, boolean[] visited, int visitedCnt) {
        // 종료 조건: 마지막날이거나 이미 모든 관광지를 방문했다면 끝
        if (day == M || visitedCnt == points.size()) {
            if (satis > maxSatis) {
                maxSatis = satis;
                // 최대 만족 경로도 전달
                maxSatisPath = new ArrayList<>(tempPath);
            }
            return;
        }

        // 다음에 가볼 지점이 있었나요???
        boolean canGoNext = false;

        for (int p = 0; p < points.size(); p++) {
            Point point = points.get(p);

            // 먼저 퇴로가 있는지 확인해봐야 한다. m-1일 이전까지는 호텔로 가고, m-1일은 공항으로 갈 수 있나 보자.
            if (!visited[point.idx]) {
                int tempTime = 0;
                if (day == M - 1) {
                    tempTime = time + graph[start.idx][point.idx] + point.time + graph[point.idx][airPort.idx];
                } else {
                    tempTime = time + graph[start.idx][point.idx] + point.time + graph[point.idx][point.nearH.idx];
                }
                // 이 시간이 540 이상이면 이 길은 못간다.
                if (tempTime > 540) {
                    continue;
                }
                // 갈 수 있다면 그 시간만큼만 가보자..
                canGoNext = true;
                visited[point.idx] = true;
                tempTime = time + graph[start.idx][point.idx] + point.time;
                tempPath.push(point.idx);
                sol(day, point, satis + point.satis, tempTime, visited, visitedCnt + 1);
                tempPath.pop();
                visited[point.idx] = false;
            }
        }
        // 위의 for를 타고 다른 재귀로 못갔다면. 갈곳이 없는것
        // 갈 곳이 없었다면 호텔이나 공항 가기. 이쪽은 중복 방문이 가능하기 때문에 vistied 체크 불필요 - 날이 바뀌면서 시간은 reset
        if (!canGoNext) {
            if (day == M - 1) {
                tempPath.push(airPort.idx);
                sol(day + 1, airPort, satis, 0, visited, visitedCnt);
                tempPath.pop();
            }
            // 그렇지 않다면 호텔로 가는데 가까운 호텔만 가는것은 아니다.. - 가까운 호텔의 기준은 관광지 한번 더 볼 수 있나?
            else {
                for (int h = 0; h < hotels.size(); h++) {
                    Point hotel = hotels.get(h);
                    if (time + graph[start.idx][hotel.idx] <= 540) {
                        tempPath.push(hotel.idx);
                        sol(day + 1, hotel, satis, 0, visited, visitedCnt);
                        tempPath.pop();
                    }
                }
            }
        }
    }

    static class Point {
        String type; // 타입
        int idx, time, satis; // 인덱스, 즐기는 시간, 만족도
        Point nearH; // 가까운 호텔 정보

        public Point(String type, int idx, int time, int satis, Point nearH) {
            super();
            this.type = type;
            this.idx = idx;
            this.time = time;
            this.satis = satis;
            this.nearH = nearH;
        }

        @Override
        public String toString() {
            return type + ", idx=" + idx + ", time=" + time + ", satis=" + satis + ", nearH=" + nearH;
        }
    }


    static String src = "1\r\n" +
                        "10 3\r\n" +
                        "60 90 100 110 240 40 30 60 30\r\n" +
                        "60 120 140 200 120 100 60 60\r\n" +
                        "90 110 170 100 100 30 90\r\n" +
                        "50 110 40 80 90 90\r\n" +
                        "70 30 50 90 90\r\n" +
                        "100 140 180 120\r\n" +
                        "40 90 40\r\n" +
                        "100 20\r\n" +
                        "70\r\n" +
                        "A\r\n" +
                        "P 240 6\r\n" +
                        "P 120 4\r\n" +
                        "P 240 5\r\n" +
                        "P 60 4\r\n" +
                        "P 200 6\r\n" +
                        "P 180 1\r\n" +
                        "P 180 1\r\n" +
                        "H\r\n" +
                        "H";
}
/*
 * 
 * 1 2 3 4 5 6 7 8 9 10 A 1 0 60 90 100 110 240 40 30 60 30 P 240 6 2 60 0 60
 * 120 140 200 120 100 60 60 P 120 4 3 90 60 0 90 110 170 100 100 30 90 P 240 5
 * 4 100 120 90 0 50 110 40 80 90 90 P 60 4 5 110 140 110 50 0 70 30 50 90 90 P
 * 200 6 6 240 200 170 110 70 0 100 140 180 120 P 180 1 7 40 120 100 40 30 100 0
 * 40 90 40 P 180 1 8 30 100 100 80 50 140 40 0 100 20 H 9 60 60 30 90 90 180 90
 * 100 0 70 H 10 30 60 90 90 90 120 40 20 70 0
 */