[코틀린, 자바] 백준 2273 - 줄 서기 (boj kotlin java)

문제 : boj2273

 

1. 알아야 하는 것

  총 5명이 있다고 가정하고 내 앞에 서야 한다고 확정된 학생이 2명이고, 내 뒤에 서야 한다고 확정된 학생이 1명이라고 해보자. 이 정보를 가지고  '각 학생이 설 수 있는 위치의 범위'를 알 수 있을까? 내 앞에 최소 2명은 있어야 하므로 난 무조건 3번째 자리 이상으로 서야 한다. 또한 내 뒤에 반드시 한 명은 있어야 하므로 4번째 이하의 자리에 서야만 한다(5-1=4). 따라서 '설 수 있는 위치의 범위'는 '3 4'가 된다.

 

  즉, 자신의 앞이라고 확정된 인원이 X명, 자신의 뒤라고 확정된 인원이 Y명, 총 N명이라면 범위는 'X+1 N-Y'가 됨을 알 수 있다.

 

  그럼 다음의 경우를 생각해보자.

3 2
1 2
2 3

위의 경우 3의 앞에 2가 서고, 2의 앞에 1이 선다. 데이터 상으로는 3의 앞에 2 한명이 확정이지만, 2의 앞에도 1이 서므로 3의 앞에는 2명이 확정된 것이라 볼 수 있다. 즉, 위의 경우 범위라고 할 것도 없이 모두의 위치가 확정된다(순서대로 '1 1', '2 2', '3 3'이 될 것이다).

 

  위의 내용들을 종합해볼 때 종합해볼 때 우리가 이 문제를 풀기 위해 '알아야 하는 것'은 모든 학생들 각각에 대해 자신의 앞, 자신의 앞의 앞, ... , 자신의 뒤, 자신의 뒤의 뒤, ... 와 같이 앞뒤로 확정된 모든 인원의 수를 알 수 있어야 한다.

 

 

2. 어떻게 알 수 있을까?

  입력으로 주어지는 데이터 A, B를 방향 그래프(Directed Graph)로 바꿔서 생각해보자. A->B, A<-B 방향은 상관없다. 자신의 원하는 대로 방향을 정하자. 내 경우엔 A->B로 방향을 정했다. 즉, 간선이 생긴 경우 간선의 방향이 '더 앞에 섬'->'더 뒤에 섬' 이라는 뜻이다. 예제 1을 확인해보자.

//예제 입력 1
3 2
1 3
2 3

  그래프로 그리면 위와 같다. 1단계밖에 진행이 안되므로 눈으로도 충분히 쫒으면서 확인할 수 있다. 자신의 앞이라고 확정된 인원이 X명, 자신의 뒤라고 확정된 인원이 Y명이라고 하자. 1은 X=0, Y=1 / 2는 X=0, Y=1 / 3은 X=2, Y=0 이다. 따라서 위에서 설명한 것과 같이 'X+1 N-Y'를 출력해주면 정답이 맞다.

 

  위의 예시는 너무 간단하니 다음의 예시를 확인해보자.

5 5
1 2
2 3
4 2
2 5
3 5

그래프로 그려보면 다음과 같다. 이건 눈으로 봐도 쉽사리 답을 파악하기 어려울 것이다.

  여기서 자신의 앞의 앞, 앞의 앞의 앞,... ,뒤의 뒤, ... 이런것들을 어떻게 파악할 수 있을까? 단순히 그래프 탐색을 하면 된다! 1에서 도달할 수 있는 모든 위치인 2,3,5는 자신의 뒤이다. 3으로 도달할 수 있는 모든 위치인 1,2,4는 자신의 앞이다(A->B가 아니라, A<-B로 간선 방향을 설정했다면 그 반대이다.). 따라서 입력으로 주어진 M개의 간선을 가지고 모든 정점에서 출발해서 그래프 탐색을 마치면 모든 정점에 대해 자신의 앞과 뒤를 셀 수 있다. 정점n(1<=n<=N)에서 도달 가능한 정점의 수를 outCnt(자신의 뒤 확정), 정점n으로 도달 가능한 정점의 수를 inCnt(자신의 앞 확정)라고 하면 위의 예시에 대해 센 결과는 다음과 같다.

  그리고 위에서 설명한 바와 같이 답은 'inCnt+1 N-outCnt'가 될 것이다. 답은 다음과 같다.

1 2
3 3
4 4
1 2
5 5

  이 때 그래프 탐색은 bfs나 dfs로 해도 시간복잡도 상에 큰 문제는 없으나, 이렇게 N이 오랜만에 작을 때는 평소 쓰기 힘들지만(O(N^3)이라서 문제 출제자가 허락해준 특정 경우에만 쓸 수 있다 ㅋㅋ) 가장 구현이 편하고 강력한 플로이드 와샬을 써주는게 날먹하는 기분이 들어서 좋다. (자바코드에서 21~28line, 코틀린 코드에서 18~25line이 플로이드 와샬 부분)

 

 

3. 예외처리

  20%대면 보통 사악한 문제가 많다. 이 문제에서 내 생각엔 처리할게 사이클이 생기는 경우밖에 없었다. 그래서 설마 이것만 처리한다고 되겠어? 싶었는데 허무하게 통과했다. 아마 누군가가 맞왜틀을 엄청나게 했을 것 같다.. ㅠ

 

  아무튼 예외처리해야할 부분은 다음과 같은 경우이다.

3 3
1 2
2 3
3 1

위와 같은 경우 사이클이 발생하고, 1의 뒤에 3이 서야하지만 3의 뒤에 1이 서야하는 문제가 생긴다.

이걸 어떻게 판단할까? 간단하게 예를들면 1에서 5로 탐색이 가능한데, 5에서도 1로도 탐색이 가능하면 사이클이 생긴 경우이다.

 

 

 

코드(kotlin) : github

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer
import kotlin.math.min

const val INF = 257
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var st = StringTokenizer(readLine())
    val n = st.nextToken().toInt()
    var m = st.nextToken().toInt()
    val arr = Array(n){IntArray(n){INF}}
    repeat(m) {
        st = StringTokenizer(readLine())
        val a = st.nextToken().toInt()-1
        val b = st.nextToken().toInt()-1
        arr[a][b] = 1
    }
    for (k in 0 until n) {
        for (i in 0 until n) {
            for (j in 0 until n) {
                if (i == j || arr[i][k] == INF || arr[k][j] == INF) continue
                arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j])
            }
        }
    }
    val sb = StringBuilder()
    for (i in 0 until n) {
        var outCnt = 0
        var inCnt = 0
        for (j in 0 until n) {
            if (i == j) continue
            if (arr[i][j] != INF && arr[j][i] != INF) return println(-1)
            if (arr[i][j] != INF) outCnt++
            if (arr[j][i] != INF) inCnt++
        }
        sb.append(inCnt+1).append(' ').append(n-outCnt).append('\n')
    }
    print(sb)
}

 

코드(java) : github

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

public class Main {
    private static final int INF = 257;
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] arr = new int[n][n];
        for (int i = 0; i < n; i++) Arrays.fill(arr[i], INF);
        while (m-->0) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            arr[a][b] = 1;
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == j || arr[i][k] == INF || arr[k][j] == INF) continue;
                    arr[i][j] = Math.min(arr[i][j], arr[i][k]+arr[k][j]);
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            int outCnt = 0;
            int inCnt = 0;
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (arr[i][j] != INF && arr[j][i] != INF) {
                    System.out.println(-1);
                    return;
                }
                if (arr[i][j] != INF) outCnt++;
                if (arr[j][i] != INF) inCnt++;
            }
            sb.append(inCnt+1).append(' ').append(n-outCnt).append('\n');
        }
        System.out.print(sb);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}