백준 11265[자바] java 끝나지 않은 파티

 

문제 링크: https://www.acmicpc.net/problem/11265

11265번: 끝나지 않는 파티

 

▶문제

파티를 좋아하는 민호는 끝없이 파티가 열리는 놀이동산 "민호 월드"를 세웠다. 처음에는 한 개의 파티장만을 가지고 있는 작은 놀이동산이었지만, 사람들의 점점 많이 찾아와 파티장을 증축했고 현재는 N개의 파티장을 가진 큰 놀이동산이 되었다. 민호는 파티장을 증축할 때마다 편의를 위해 새로운 파티장과 기존의 모든 파티장이 직접적으로 연결이 될 수 있는 도로들을 만들었다. 이때 만들어진 도로들은 사용자들의 편의를 위해 일방통행으로 설계가 되었다.

파티장이 적을때는 괜찮았지만 파티장이 많아진 지금 다음과 같은 두 가지 문제점이 발생했다.

1. A 파티장에서 B 파티장으로 빨리 갈 수 있도록 직접 연결이 된 일방통행 도로를 만들었지만 A와 B가 아닌 다른 파티장을 경유해서 더 빨리 갈 수 있는 경우가 있을 수 있다.
2. 지금으로부터 C만큼의 시간 뒤에 B번 파티장에서 새롭게 파티가 열리는데 1번과 같은 이유 때문에 현재 있는 A파티장에서 B번 파티장까지 파티가 열리는 시간까지 맞춰 갈 수 있는지 쉽게 알 수 없다.

이러한 문제점으로 이용객들의 불만이 점점 커져갔고 민호는 이를 해결하기 위해 빠른 네비게이션 서비스를 실행하기로 하였으나 서비스 요청이 너무 많아 업무가 마비되기에 이르렀다. 이에 민호는 천재 프로그래머인 당신에게 이 문제를 해결해 달라고 요청하였다. 민호를 도와한 파티장에서 다른 파티장에까지 시간 내에 도착할 수 있는지 없는지 알아봐 주는 프로그램을 작성하자.

▶입력

입력의 첫 번째 줄에는 파티장의 크기 N(5 ≤ N ≤ 500)과 서비스를 요청한 손님의 수 M(1 ≤ M ≤ 10,000) 이 주어진다. 각각의 파티장은 1번부터 N번까지 번호가 붙여져 있다. 다음에는 N개의 줄에 걸쳐 각각 N개의 수가 주어진다. i번째 줄의 j번째 수 T(1 ≤ T ≤ 1,000,000)는 i번 파티장에서 j번 파티장으로 직접적으로 연결된 도로를 통해 이동하는 시간을 의미한다.

다음 M개의 줄에는 세개의 정수 A, B, C가 주어진다. A(1 ≤ A ≤ N)는 서비스를 요청한 손님이 위치한 파티장의 번호, B(1 ≤ B ≤ N) 다음 파티가 열리는 파티장의 번호, C(1 ≤ C ≤ 1,000,000,000)는 지금으로부터 다음 파티가 열리는 데 걸리는 시간을 의미한다.

▶출력

M개의 줄에 걸쳐 서비스를 요청한 손님이 시간내에 다른 파티장에 도착할 수 있으면 “Enjoy other party”를, 시간 내에 도착할 수 없으면 "Stay here”를 출력한다.

▶해설

최단 경로 알고리즘들을 활용해서 풀 수 있는 문제입니다. 다익스트라를 이용하겠습니다. 조건을 살펴보겠습니다.

 

1. 임의로 주어진 시작점 -> 끝점으로 정해진 시간안에 갈 수 있는지

2. 우회해서 도착하는 것도 인정

 

우선 걸리는 시간을 담을 List<Node>[]를 담아줍니다. 자신에서 자신에게로 가는 것은 제외해줍니다.

Node 클래스는 끝점과 걸리는 시간입니다. List를 배열 형태로 선언해서 list [시작점]. add(Node(끝점, cost))로 담아줍니다. 

 

for(int i=1; i<=n; i++){
    String[] s1 = br.readLine().split(" ");
    for(int j=0; j<s1.length; j++){
        if(i==j+1){
            continue;
        }
        list[i].add(new Node(j+1,Integer.parseInt(s1[j])));
    }
}

 

사용자의 입력이 있을때마다 가능한지 체크한다면 시간 초과가 발생합니다. 따라서 2차원 배열 time [][]을 선언합니다.

time [시작점][끝점]=cost로 하여금 다익스트라를 적용합니다.

우선순위 큐를 이용하고, 정렬조건은 cost가 낮은 순서입니다. 

private static void check(int start){
    PriorityQueue<Node> queue = new PriorityQueue<>();
    queue.add(new Node(start,0));

    Arrays.fill(time[start],Integer.MAX_VALUE);
    boolean [] check = new boolean[n+1];
    while(!queue.isEmpty()){
        Node poll = queue.poll();
        if(!check[poll.end]){
            for(Node next: list[poll.end]){
                if(time[start][next.end]>poll.cost+ next.cost){
                    time[start][next.end] = poll.cost+next.cost;
                    queue.add(new Node(next.end,poll.cost+ next.cost));
                }
            }
        }
    }
}

 

time에 대한 배열을 모두 구했다면 사용자에 입력에 대해 time [시작점][끝점]<=limit를 판별해주고, StringBuilder에 넣어줍니다.

for(int i=0; i<m; i++){
    String[] s1 = br.readLine().split(" ");
    int start = Integer.parseInt(s1[0]);
    int end = Integer.parseInt(s1[1]);
    int limit = Integer.parseInt(s1[2]);
    if(time[start][end]<=limit){
        sb.append("Enjoy other party").append("\n");
    }
    else{
        sb.append("Stay here").append("\n");
    }
}

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.lang.*;

class Node implements Comparable<Node>{
    int end;
    int cost;

    public Node(int end, int cost) {
        this.end = end;
        this.cost = cost;
    }

    @Override
    public int compareTo(Node o) {
        return this.cost-o.cost;
    }
}

public class Main {

    static int n,m;
    static List<Node> [] list;
    static int [][] time;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);

        time = new int[n+1][n+1];
        list = new ArrayList[n+1];


        for(int i=1; i<=n; i++){
            list[i] = new ArrayList<>();
        }

        for(int i=1; i<=n; i++){
            String[] s1 = br.readLine().split(" ");
            for(int j=0; j<s1.length; j++){
                if(i==j+1){
                    continue;
                }
                list[i].add(new Node(j+1,Integer.parseInt(s1[j])));
            }
        }

        StringBuilder sb = new StringBuilder();

        for(int i=1; i<=n; i++){
            check(i);
        }

        for(int i=0; i<m; i++){
            String[] s1 = br.readLine().split(" ");
            int start = Integer.parseInt(s1[0]);
            int end = Integer.parseInt(s1[1]);
            int limit = Integer.parseInt(s1[2]);
            if(time[start][end]<=limit){
                sb.append("Enjoy other party").append("\n");
            }
            else{
                sb.append("Stay here").append("\n");
            }
        }

        System.out.println(sb.toString());

    }

    private static void check(int start){
        PriorityQueue<Node> queue = new PriorityQueue<>();
        queue.add(new Node(start,0));

        Arrays.fill(time[start],Integer.MAX_VALUE);
        boolean [] check = new boolean[n+1];
        while(!queue.isEmpty()){
            Node poll = queue.poll();
            if(!check[poll.end]){
                for(Node next: list[poll.end]){
                    if(time[start][next.end]>poll.cost+ next.cost){
                        time[start][next.end] = poll.cost+next.cost;
                        queue.add(new Node(next.end,poll.cost+ next.cost));
                    }
                }
            }
        }
    }
}