[백준 1613번/JAVA] 역사 (문제 풀이, 코드)

역사

[문제]

문제가 길지 않다. 시간 제한 2 초, 메모리제한 128MB 널널하다.

사건의 개수 N, 전후 관계의 개수 K, 궁금한 관계의 수 S 

 

[풀이]

질문 게시판을 보면 해당 문제를 BFS나 Union-Find로 풀려고 했으나 시간초과 메모리초과 문제를 겪는 사람들이 있다.

해당 문제는 플로이드-와샬 알고리즘을 이용하는 문제로 나는 아마 처음 들어보는(예전에 썼더라도 기억이 안 나는) 알고리즘 이었다.

플로이드-와샬 알고리즘이란?

DP(dynaminc programming)의 일종으로 어떤 점을 경유지로 거쳐 시작점에서 도착점까지의 최단 거리를 구하는 알고리즘이다. 모든 꼭짓점 i에서 모든 꼭짓점 j로, 모든 꼭짓점 k를 거쳐서 가는 최단 거리를 구하는 것.이 알고리즘의 의사코드는 간결하다. for문 3개면 끝이다. (아래 링크  참고)ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

플로이드-워셜 알고리즘 - 위키백과, 우리 모두의 백과사전

 

[내 코드 알고리즘]

내용

1. 첫 번째 for문은 c, 경유지를 나타낸다.
2. 두 번째 for문은 a, 출발지를 나타낸다.
3. 세 번째 for문은 b, 도착지를 나타낸다.
4. 만약 경유지 == 출발지면 continue;
5. a->b의 관계를 모를 때, a->c에서 a가 먼저 일어난 일이고, c->b에서 c가 먼저 일어난 일이라면 a->b는 a가 먼저 일어난 일이 된다. a보다 늦게일어난 일보다 더 늦게 일어난 일은 당연히 a보다 늦게 일어난 일!

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class history_1613 {
	static int INF = 10000;
	static int N;
	public static void main(String args[]) throws IOException{
		StringBuilder sb = new StringBuilder();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken());
		int[][] his = new int[N+1][N+1];
		init(his);
		for(int i=0; i<k; i++) {
			st = new StringTokenizer(br.readLine()," ");
			int pre = Integer.parseInt(st.nextToken()); int post = Integer.parseInt(st.nextToken());
			his[pre][post]=-1; his[post][pre]=1;
		}
		
		for(int c=1; c<=N; c++) {
			for(int a=1; a<=N; a++) {
				if (a == c) continue;
				for (int b = 1; b <= N; b++) {
					if (a == b || c == b) continue;
					if (his[a][b] == INF) {
						if (his[a][c] == 1 && his[c][b] == 1) {
							his[a][b] = 1;
							his[b][a] = -1;
						}
						/*
						else if(his[a][c]==-1 && his[c][b] == -1) {
							his[a][b] = -1; his[b][a] = 1;
						}
						*/
					}
				}
			}
		}
		
		
		int s = Integer.parseInt(br.readLine());
		for(int i=0; i<s; i++) {
			st = new StringTokenizer(br.readLine()," ");
			int pre = Integer.parseInt(st.nextToken()); int post = Integer.parseInt(st.nextToken());
			if(his[pre][post] == INF || his[pre][post] == 0) sb.append(0+"\n");
			else sb.append(his[pre][post]+"\n");
		}
		System.out.println(sb);
	}
	public static void init(int[][] a) {
		for(int i=0; i<=N;i++)
			for(int j=0;j<=N;j++) {
				if(i==j) a[i][j] = 0;
				else a[i][j] = INF;
			}
	}
}

 

나름 준수한 메모리 사용량과 시간.

[난관]

내용 처음 썼던 코드의 개념 자체는 비슷했다.

i->j 에서 ( 출발 , 도착, 경유 순의 for문 구성임 )

j가 i보다 늦게 일어난 일이면 j보다 늦게 일어난 일들(k)은 i에게도 늦게 일어난 일이라고 모두 체크한다.

j가 i보다 일찍 일어난 일이면, j보다 일찍 일어난 일들(k)은 i에게도 일찍 일어난 일이라고 모두 체크한다.

=> 9%인가 37%인가 어쨌든 그쯤에서 계속 틀렸음.

대체 왜 틀린거지? 대체 왜! 고민했지만 일단 늦은 밤이라서 fresh하지 못하다는 생각에 다음날 다시 풀었다.for문의 위치는 고정이고, 일어난 일에 대해서 해보거나, 아직 관계를 모르는 일에서 해보는 등을 했다.당연하게도 잘 안돼서 위키백과에 있는 플로이드-와샬의 정석적인 for 위치를 찾아보고 해당 for 위치대로 코드를 짰더니 맞았다.    ▶ 경유지가 가장 바깥 for문, 출발지가 중간 for문, 도착지가 마지막 for문

왜 for 문의 순서를 잘 지켜야 할까?

직접 손으로 해보는 게 이해가 빠르다! 직접 해보자.

원래 내 코드(경유지가 계속 변하는 방식 = 경유지가 마지막 for문)

1->3->2	1->2->3	1->2->4	2->3->1	2->1->3	2->1->4
1->4->2	1->4->3	1->3->4	2->4->1	2->4->3	2->3->4

 

 

경유지인 k가 계속 변할 것이므로 위 표처럼 진행이 된다.

0	INF	-2	INF
4	0	3	INF
INF	INF	0	2
INF	-1	INF	0

 1->3->2 불가 1->4->2 불가 1->2->3 불가 1->4->3 불가

1->2->4 불가 1->3->4 가능! 2->3->1 불가 2->4->1 불가

2->1->3 가능! 2->4->3 불가 2->1->4 가능! 2->3->4 가능

... 이렇게 모든 for문을 돌면 아래 표처럼 나온다.

0	INF	-2	0
4	0	2	4
INF	1	0	2
3	-1	1	0

 

틀린 부분은 붉은 표시를 해두었다.

왜 답이 틀리는 걸까? 이제는 생각을 해보자.

해당 알고리즘은 직접 연결된 길이 없다면 불가능이라고 끝을 내고 다음 순서로 넘어간다.

당장 굵은 표시를 친 글 부분만 봐도, 1->3->4가 나중에 업데이트 되었기 때문에 1->4->2 에서 1->4를 못간다고 인식해서 1->2도 갈 수 없게 되어 버린다.

그러니까...

경유지가 계속 바뀌기 때문에 해당 경유지를 이용하는 경로가 더 있을 수 있지만, 나중에 업데이트 될 예정이라 업데이트 되기 이전에는 해당 경유지로 갈 수 없다면 그냥 도착지로도 갈 수없다고 판단해버림!

경유지를 고정 해두면 한 번에 경유지가 업데이트 되서 그럴 일이 없다!

라는 게 나의 생각.

 

 

 

GitHub에 티스토리에 올리지 않은 코드들도 업로드 되어 있습니다.

github.com/MOBUMIN/BJalgorithm/blob/master/01000-1999/history_1613.java

MOBUMIN/BJalgorithm