BOJ 1613 역사

 

10159번: 저울 (acmicpc.net)

10159번: 저울

만약 이 저울 문제를 플로이드-워셜 알고리즘을 통해 풀었었다면 이번 문제는 간단한 응용이다.

 

저울 문제에서 기존의 플로이드-워셜 알고리즘을 이용한 부분은 상하관계를 설정하고, O(N^3) 동안 기존 거리를 구하던 공식을 바꾸는 것에서부터 시작하였다.

 

for ( int i = 1; i <= n; i++)
{
  for ( int j = 1; j <= n ; j++)
  {
    for (int k = 1; k <= n; k++)
    {
       if ( line[j][i] == 1 && line[i][k] == 1 )
       {
          line[j][k] = 1;
       }
   }
}

이게 플로이드-워셜 알고리즘의 핵심인데, 들어가는 공식이 바뀌었다.

이를 해석해보면, j와 i의 관계가 상하관계로 입증되었고, i와 k의 관계도 상하관계가 입증되었다면,

j와 k 관계 역시 상하관계가 존재한다라는 의미로 해석하면 된다.

 

이를 이용하면 저울 문제는 매우 쉽게 풀 수 있는 문제이다.

 

그러나 저울 문제와 현 문제의 차이점은 한 지점과 또 다른 한 지점의 상하 관계가 어떻게 되는지 또한 입증해야한다.

이를 해결하기 위해서 했던 생각에 대해서 먼저 서술하고자 한다.

 

1. 플로이드-워셜 알고리즘으로 인해 완성된 그래프 graph[i][j] 에서 i번째 역사를 기준으로 j번째 역사의 값이 1이라면

i번째 역사가 j번째 역사보다 먼저 일어났다는 것이 증명된다.

 

2. 그리하여 생각을 해보니, 만약 graph[i][j] , graph[j][i]가 전부 0이면 서로 상하관계를 모르는 역사가 될 것이라는 생각이 먼저 들었다.

 

3. 그 후 graph[i][j], graph[j][i]가 각각 값에 따라서 상하관계를 나타낼 수 있는 Key가 아닐까하는 생각이 들었음.

 

4. 그래서 graph[i][j] == 1이고, graph[j][i] == 0인 경우라면? i번째 역사가 j번째 역사보다 앞이므로 -1을 출력

만약 반대라면 1을 출력하면 되겠다.

 

이것이 내가 생각한 알고리즘의 방식이었고 이를 이런식으로 표현했다.

 

else if ( line[st2][en2] < line[en2][st2])
{
  bw.write("1"+"\n");
}
else
{
  bw.write("-1"+"\n");
}

기존에 생각했던 방식과는 코드는 차이가 있지만 결국 값에 따라서 1 or -1을 출력하도록 하였다. 어차피 1 or 0이기 때문에 서로가 1을 가지고 있는 것은 그래프의 특성상 없는 경우의 수이기 때문에 해당 식을 사용해 정답 판정을 받게 되었다.