백준 알고리즘 11562번 : 백양로 브레이크

링크

https://www.acmicpc.net/problem/11562

문제

서울 소재 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줄에 걸쳐 이루어진다.

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

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

예제 입력 및 출력

풀이법

한... 1시간 정도 고민하다가 안풀려서 풀이를 봤더니 새로운 접근이 필요한 문제였다.
이 문제에서는 그동안 풀었던 최단 거리를 구하는 것이 아닌.. 간선을 단방향에서 양방향으로 바꾸는데 필요한 비용을 구하는 것이 문제였다.
이 문제를 풀 때 가장 중요한 점은 단뱡향으로 들어온 간선(b == 0)은 비용을 0으로 두고 역방향은 1로 두는 관점이다.
b == 1일때는 양방향 간선이므로 dist[u][v] = 0, dist[v][u] = 0으로 놓고 b == 0일때는 u -> v로 가는 단방향 간선만 존재하므로 이것의 역방향(dist[v][u] = 1)로 놓고 플로이드 탐색을 진행하면 각 정점을 갈 때 단뱡향에서 양방향으로 바꾸어야하는 비용을 구할 수 있다.

풀이 코드(C++, 32ms)

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
#include<tuple>
#include<functional>
#include<utility>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<complex>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define MAX 251
#define INF 1e9
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;

int dist[MAX][MAX] = {};

void resetGraph(int n){
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
      dist[i][j] = i==j ? 0 : INF;
    }
  }
}

void floyd(int n){
  for(int k = 1; k <= n; k++){ // k : 거쳐가는 정점
      for(int i = 1; i <= n; i++){ // i : 행(출발 정점)
        for(int j = 1; j <= n; j++){ // j : 열(도착 정점)
         // 점화식 distance[i,j] = min(distance[i,j], distance[i,n] + distance[n,j])
          dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
  }
}

void printGraph(int n){
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n ; j++){
      if(dist[i][j] == INF) cout << 'I' << ' ';
      else cout << dist[i][j] << " ";
    }
    cout << "\n";
  }
}

int n,m,k; // 질문의 수


int main(){
  fastio;
  cin >> n >> m;
  resetGraph(n);
  for(int i = 0; i < m; i++){
    int u,v,b;
    cin >> u >> v >> b;
    if(b == 0){ // 단방향
      dist[u][v] =  0;
      dist[v][u] = 1;
    }
    else if(b == 1){ // 양방향
      dist[u][v] = 0;
      dist[v][u] = 0;
    }
  }
  floyd(n);
  cin >> k;
  for(int i = 0; i < k; i++){
    int s,e;
    cin >> s >> e;
    cout << dist[s][e] << "\n";
  }
  return 0;
}

복습 + 코드개선(28ms)

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define sz(a) int((a).size())
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using wector = vector<vector<int>>;

const int INF = int(1e9) + 1;

int dist[251][251];

void reset(int n){
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
      dist[i][j] = i==j ? 0 : INF;
    }
  }
}

void floyd(int n){
  for(int k = 1; k <= n; k++){
    for(int i = 1; i <= n; i++){
      for(int j = 1; j <= n; j++){
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }
}

int main(){
  fastio;
  int n,m,k; cin >> n >> m;
  reset(n);
  for(int i = 0; i < m; i++){
    int u,v,b; cin >> u >> v >> b;
    if(b == 0){ // 일방통행
      dist[u][v] = 0;
      dist[v][u] = 1;
    }
    else{ // 양방통행
      dist[u][v] = 0;
      dist[v][u] = 0;
    }
  }
  floyd(n);
  cin >> k;
  while(k--){
    int s,e; cin >> s >> e;
    cout << dist[s][e] << "\n";
  }
  return 0;
}