문제
풀이 방법
처음 접근 방식
처음에는 BFS로 접근했었다. 그래프 문제인건 확실했고, 최단거리를 통해서 갈 수 있는지 여부를 확인해야했기 때문이다.
아래가 내가 처음에 작성한 코드이다.
package algo;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class p11265 {
static List<Node> [] arr;
static int N = 0;
static long cnt = 0;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
//1 입력 받기
// 1-1. N과 M 입력 받기
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); // 파티장의 개수(1~)
int M = Integer.parseInt(st.nextToken()); // 사람 수 (1~)
// 1-2. 진입 배열 만들기
arr = new List[N+1];
//초기화
for(int i=1; i<N+1; i++) arr[i] = new ArrayList<>();
// 진입 배열로 만들기
for(int t = 1; t<=N; t++) {
st = new StringTokenizer(br.readLine());
for(int j=1; j<N+1; j++) {
int now = Integer.parseInt(st.nextToken());
if(now!=0) {
arr[j].add(new Node(now, t));
}
}
}
// 손님들 배열 만들기
Person [] p = new Person[M+1];
for(int i = 1; i<=M; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int time = Integer.parseInt(st.nextToken());
p[i] = new Person(start, end, time);
}
//손님들 배열 순회
for(int i=1; i<M+1; i++) {
if(calculate(p[i], new boolean[N+1], p[i].time) <= p[i].time) {
sb.append("Enjoy other party\n");
}else {
sb.append("Stay here\n");
}
}
bw.write(sb.toString());
bw.flush();
bw.close();
}
// 걸리는 시간을 계산하는 메서드
static long calculate(Person p, boolean[] visited, long maxTime) {
int start = p.start; // 목적지
int end = p.end; // 현재 위치
long time = 0; // 걸리는 시간
//end -> start로 가야함
Queue<Person> q = new LinkedList<>();
for(Node n : arr[end]) {
q.add(new Person(start, n.from, time + n.weight));
}
long min = Long.MAX_VALUE;
while(!q.isEmpty()) {
Person poll = q.poll();
visited[poll.end] = true;
// 만약 도착했으면
if(poll.start == poll.end) {
// min보다 작으면 업데이트
if(min > poll.time) min = poll.time;
}else { //도착하지 않았으면
for(Node n : arr[end]) { //자기 자신으로 진입가능한 것들 중에서
if(!visited[n.from] && maxTime >= (poll.time + n.weight)) {
q.add(new Person(start, n.from, poll.time + n.weight));
}
}
}
}
return min;
}
}
class Node{
int weight;
int from;
public Node(int weight, int next) {
this.weight = weight;
this.from = next;
}
}
class Person{
int start;
int end;
long time;
public Person(int start, int end, long time) {
this.start = start;
this.end = end;
this.time = time;
}
}
그런데 시간초과가 났다.
위 코드를 보면 calculate()에서 아래 코드 부분이 O(N * N)이다.
while(!q.isEmpty()) {
Person poll = q.poll();
visited[poll.end] = true;
// 만약 도착했으면
if(poll.start == poll.end) {
// min보다 작으면 업데이트
if(min > poll.time) min = poll.time;
}else { //도착하지 않았으면
for(Node n : arr[end]) { //자기 자신으로 진입가능한 것들 중에서
if(!visited[n.from] && maxTime >= (poll.time + n.weight)) {
q.add(new Person(start, n.from, poll.time + n.weight));
}
}
}
}여기서는
N이 500이다. 그런데calculate()를M만큼 반복하므로O(500 * 500 * 100,000)이다. 따라서200,000,000을 넘으므로 시간초과가 나는 것이다.
최종 해결 방안
결국 나는 플로이드 워셜 알고리즘을 사용해야한다는 것을 알았다. O(V^3)이긴 하지만 V가 500이므로 충분히 가능하다. 따라서 플로이드 워셜 알고리즘을 사용하여 해결했다.
1. 입력을 받아 2차원 거리 배열 만들기
플로이드 워셜은 2차원 배열을 선언해야한다. 이후 행과 열을 각각 출발 노드와 목적지 노드로 생각하며 문제를 해결한다. 따라서 2차원 배열을 선언하였다.
또한 각 배열의 초기값은 -1로 초기화하고(일반적으로 무한대로 하지만 여기서는 음수 값이 주어지지 않으므로 편의상 -1로 했다), 행과 열이 같으면 자기 자신 노드로 가는 경우이므로 0으로 초기화했다.
이후 2차원 배열에 거리 입력 값을 받았다.
//1 입력 받기
// 1-1. N과 M 입력 받기
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 파티장의 개수(1~)
int M = Integer.parseInt(st.nextToken()); // 사람 수 (1~)
long [][] arr = new long [N+1][N+1];
// 자기 자신은 0으로 초기화하고 나머지는 -1로 초기화
for(int i=1; i<=N; i++) {
for(int j=1; j<=N; j++) {
if(i==j) arr[i][j] = 0;
else arr[i][j] = -1;
}
}
// 각 거리 입력 받기
for(int i=1; i<N+1; i++) {
st = new StringTokenizer(br.readLine());
for(int j=1; j<N+1; j++) {
arr[i][j] = Long.parseLong(st.nextToken());
}
}2. 플로이드 워셜을 사용하여 거리 배열 업데이트 하기
플로이드 워셜은 아래와 같은 3중 for문으로 이루어진다.
for(1 ~ N) { //K에 대해서 (중간 노드)
for(1 ~ N){ // S에 대해서(출발 노드)
for(1 ~ N){ // E에 대해서(목적지 노드)
}
}
}따라서 위 구조를 따라서 아래 코드처럼 거리 배열을 업데이트하였다.
//플로이드워셜로 거리 배열 업데이트
for(int k=1; k<=N; k++) { // K
for(int s=1; s<=N; s++) { // S
for(int e=1; e<=N; e++) { // E
arr[s][e] = Math.min(arr[s][e], arr[s][k] + arr[k][e]);
}
}
}3. 각 손님에 대해 거리 배열을 참조하여 파티 참석 여부 출력하기
플로이드 워셜 알고리즘을 통해서 거리배열이 완성되었으므로 이제 각 손님에 대해서 해당 파티가 참석 가능한지 출력하는 코드를 작성했다.
//손님들에 따라 가능한지 여부 출력하기
for(int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
long limitTime = Long.parseLong(st.nextToken());
if(limitTime >= arr[start][end]) { //시간 안에 가는 경우
sb.append("Enjoy other party\n");
}else { //시간 안에 못가는 경우
sb.append("Stay here\n");
}
}정답 코드
package algo;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class p11265_2 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
//1 입력 받기
// 1-1. N과 M 입력 받기
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 파티장의 개수(1~)
int M = Integer.parseInt(st.nextToken()); // 사람 수 (1~)
long [][] arr = new long [N+1][N+1];
// 자기 자신은 0으로 초기화하고 나머지는 -1로 초기화
for(int i=1; i<=N; i++) {
for(int j=1; j<=N; j++) {
if(i==j) arr[i][j] = 0;
else arr[i][j] = -1;
}
}
// 각 거리 입력 받기
for(int i=1; i<N+1; i++) {
st = new StringTokenizer(br.readLine());
for(int j=1; j<N+1; j++) {
arr[i][j] = Long.parseLong(st.nextToken());
}
}
//플로이드워셜로 거리 배열 업데이트
for(int k=1; k<=N; k++) { // K
for(int s=1; s<=N; s++) { // S
for(int e=1; e<=N; e++) { // E
arr[s][e] = Math.min(arr[s][e], arr[s][k] + arr[k][e]);
}
}
}
//손님들에 따라 가능한지 여부 출력하기
for(int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
long limitTime = Long.parseLong(st.nextToken());
if(limitTime >= arr[start][end]) { //시간 안에 가는 경우
sb.append("Enjoy other party\n");
}else { //시간 안에 못가는 경우
sb.append("Stay here\n");
}
}
bw.write(sb.toString());
bw.flush();
bw.close();
}
}
사용자의 입장에서 생각하며 문제를 해결하는 백엔드 개발자입니다✍