백준 11562번 - 백양로 브레이크 Java

문제

 

서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공사가 진행되면서 어떻게 한 건진 알 수 없지만 일방통행만 가능한 길이 많이 늘고 말았다.

컴퓨터과학과 학생 남규는 전공 수업을 듣고 교양 수업을 들으러 가던 중 길을 잃어 3일 밤낮을 헤매다가 공학관에서 종합관으로 가는 길은 존재하지 않는다는 결론을 내렸다.

3일 사이에 과제도 내지 못하고 출석도 하지 못해 학사경고 위기에 처한 남규는 전공을 살려 현재 일방통행인 길들 중 반드시 양방향으로 바꿔야만 하는 길이 몇 개인지 조사해 학교에 건의하기로 마음을 먹었다.

남규는 여러 건물들 사이를 직접 잇는 길들을 모두 조사했고, 그 중 어떤 길들이 일방통행인지, 또는 양방향 통행이 가능한지를 모두 체크했다.

남규의 프로그램은 간단하다. 출발지와 도착지를 입력하면 도착지까지 가기 위해 최소 몇 개의 길을 양방향으로 바꿔야만 하는지를 출력해준다. 프로그램이 완성되었다는 소문이 퍼지자, 남규처럼 길을 잃고 헤맨 경험이 있는 학생들은 남규에게 묻기 시작했다.

"공학관에서 대강당 갈 수 있어?"

"상경대 별관에서 학관으로는?"

남규는 매번 손으로 타이핑해 입력하고 결과를 보내주는 데에 지치고 말았다.

결국 앓아누운 남규를 위해 학생들의 질문을 해결할 새로운 프로그램을 만들어보자.

---

입력

 

첫 줄에 Y대학교 건물의 수 n과 길의 수 m이 주어진다. (n ≤ 250, m ≤ n * (n - 1) / 2 )

다음 m줄에 걸쳐, u v b (1 ≤ u ≤ n, 1 ≤ v ≤ n, u != v, b = 0 또는 1) 의 형태로 길에 대한 정보가 주어진다.

b가 0일 경우 u에서 v로 가는 일방통행 길인 것이고, b가 1일 경우 u와 v를 잇는 양방향 길이다.

어떤 두 건물 사이를 잇는 길은 최대 한 개이다.

다음 줄에 학생들의 질문의 수 k가 주어진다. (1 ≤ k ≤ 30,000)

다음 k줄에 걸쳐 s e (1 ≤ s ≤ n, 1 ≤ e ≤ n)의 형태로 학생들의 질문들이 주어진다.

이는 질문한 학생이 건물 s에서 건물 e로 가고 싶다는 의미이다.

---

출력

 

 

출력은 k줄에 걸쳐 이루어진다.

각 질문에 대해, 최소 몇 개의 일방통행인 길을 양방향 통행으로 바꿔야 출발지에서 도착지로 갈 수 있는지를 출력한다.

모든 길을 양방향으로 바꾸더라도 서로 도달 불가능한 건물은 없다.

---

해결 방법

 

우선 입력으로 주어진 예제를 분석해보자.

 

예제 입력으로 주어진 학교엔 건물이 4개 존재하고, 길이 3개 존재한다. 입력으로 주어진 모든 길을 그래프로 그려보면 다음과 같다.

 

예제 그래프

문제에서는 k 개의 질문이 주어지고, 각 질문마다 시작 건물과 도착 건물이 주어진다. 시작 건물에서 도착건물까지 가려고 할 때, 최소한 몇 개의 길을 양방향으로 바꿔야 주어진 도착지에 도착할 수 있는지 묻는 문제다.

 

1번에서 4번을 간다고 했을 때 몇 개의 길을 지나는지는 상관없고, 주어진 길을 따라 4번에 도착할 수 있기 때문에 정답은 0이 된다 -> 양방향으로 바꾼 길이 아무것도 없다. 

하지만 2에서 1로 간다고 가정해보자. 당장 2에서 1로 갈 수 있는 방법은 1->2 로 향하는 길을 양방향 길로 바꿔서, 2->1 로 가는 수 밖에 없다. 이 경우 답은 1이 된다.

 

단방향 길이 주어졌을 때

즉 1에서 2로 가는 단방향 길이 주어졌을 때, 1 -> 2로 가는 길의 가중치는 없지만 (지나는 길의 거리나, 개수를 묻는 것이 아니기 때문에) , 1->2 로 가는 길은 우리가 임의로 양방향 길로 변경할 수 있기 때문에 2->1로 가는 길도 있다고 가정하고 양의 가중치를 설정하면 된다.

 

양방향 길로 바꾼 최소한의 수가 정답이기 때문에 계산의 편리함을 위해 가중치를 1로 두자. 

 

즉 1->2 가중치 : 0 , 2->1 가중치 : 1이라는 엣지가 생성된다. 

 

양방향 길이 주어졌을 때

2에서 3으로 가는 양방향 길이 주어졌을 때, 2와 3 사이는 자유롭게 지나다닐 수 있으므로, 2->3 과 3->2 로 가는 가중치가 0인 엣지를 생성하면 된다.

 

 

양방향 길로 바꿀 수 있음을 생각해서 다시 그래프를 그려보면 다음과 같다.

 

플로이드 알고리즘

 가중치가 1인 간선을 지나는 건 양방향으로 바꾼 길의 개수가 1 늘어났다는 뜻이므로, 가중치가 1인 간선을 최소한으로 지나가면서 도착점에 도달하면 된다. 

 

즉, 최소한의 거리로 도착점에 도달하는 알고리즘을 사용해야 하는데, 이 문제의 경우 모든 정점이 출발점과 도착점이 될 수 있으므로 플로이드 알고리즘을 사용해 문제를 해결하자. 

 

그래프 초기화

graph = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
    Arrays.fill(graph[i], INF);
    graph[i][i] = 0;
}

 

우선 GRAPH 를 초기화하자. 1에서 1로 가는 질문도 들어오기 때문에, 꼭 i->i 를 0으로 초기화해주자.

 

입력값으로 간선 생성

for (int i = 0; i < m; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    int u = Integer.parseInt(st.nextToken()); //시작 건물
    int v = Integer.parseInt(st.nextToken()); //도착 건물d
    int b = Integer.parseInt(st.nextToken()); //0이면 일방통행, 1이면 양방향통행
    if (b == 0) {
        graph[u][v] = 0;
        graph[v][u] = 1;
    } else {
        graph[u][v] = 0;
        graph[v][u] = 0;
    }
}

이제 m 개의 길을 입력받으며, 그래프를 마저 초기화해주면 된다. 만약 일방통행 간선이 들어오면, u->v 가중치는 0으로, v->u 가중치는 1로 설정해준다. 양방향 길이 들어오면 모두 가중치를 0으로 설정해준다.

 

플로이드 알고리즘으로 답을 구하자.

static void floyd(int n) {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            if (k == i) continue;
            for (int j = 1; j <= n; j++) {
                if (k == j || i == j) continue;
                if (graph[i][j] > graph[i][k] + graph[k][j]) {
                    graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }
}

 

이제 전형적인 플로이드 알고리즘으로 답을 구하면 끝난다. 

 

1에서 1을 거쳐가는 경우를 계산하거나 (k==i) , 1에서 3을 거쳐 3으로 가는등의 경우 ( k==j || i==j) 는 불필요하니 

최적화를 위해 조건문으로 빠져나가도록 하자.