체뚱로그
[백준/C++] 11562 - 백양로 브레이크 본문
풀이 시간: 35:02
시간 복잡도: O(n^3)
공간 복잡도: O(n^2)
문제
서울 소재 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줄에 걸쳐 이루어진다.
각 질문에 대해, 최소 몇 개의 일방통행인 길을 양방향 통행으로 바꿔야 출발지에서 도착지로 갈 수 있는지를 출력한다.
모든 길을 양방향으로 바꾸더라도 서로 도달 불가능한 건물은 없다.
문제 풀이
오류 원인: 시간초과 - endl 을 ‘\n’로 바꿔주었더니 됨
전체 코드
/**
* 풀이 시간: 35:02
* 시간 복잡도: O(n^3)
* 공간 복잡도: O(n^2)
* 참고 자료: https://velog.io/@yoohoo030/%EB%B0%B1%EC%A4%8011562-%EB%B0%B1%EC%96%91%EB%A1%9C-%EB%B8%8C%EB%A0%88%EC%9D%B4%ED%81%AC
* [오류 원인]: 시간초과 - endl 을 ‘\n’로 바꿔주었더니 됨
*/
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e9;
int n, m, k;
vector<vector<int>> dist;
// 플로이드 워셜 알고리즘을 통해 모든 경로에 대하여 최단 경로 설정
void floydWarshall() {
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(void) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
dist = vector<vector<int>>(n + 1, vector<int>(n + 1, INF)); // 전부 무한대로 초기화
// 자신으로부터 자신까지의 거리는 0으로 설정
for (int i = 1; i <= n; i++) dist[i][i] = 0;
for (int i = 0; i < m; i++) {
int u, v, b;
cin >> u >> v >> b;
// 일방통행일 경우, 기존 경로로 가는 경우에는 경로를 추가할 필요가 없기 때문에 가중치 0
// 만약 일방통행 길에서 반대로 된 길을 걸었을 때에는 경로를 1개 추가해야 함
if (b == 0) { dist[u][v] = 0; dist[v][u] = 1; }
// 양방향일 경우, 각 방향에 대하여 경로를 따로 추가할 필요가 없기 때문에 가중치 0
if (b == 1) { dist[u][v] = 0; dist[v][u] = 0; }
}
floydWarshall();
cin >> k;
for (int i = 0; i < k; i++) {
int s, e;
cin >> s >> e;
cout << dist[s][e] << '\n';
}
}
https://www.acmicpc.net/problem/11562
'PS > BOJ' 카테고리의 다른 글
[백준/C++] 1092 - 배 (0) | 2024.01.09 |
---|---|
[백준/C++] 1719 - 택배 (0) | 2023.12.28 |
[백준/C++] 1277 - 발전소 설치 (0) | 2023.12.28 |
[백준/C++] 14938 - 서강그라운드 (0) | 2023.12.19 |
[백준/C++] 11265 - 끝나지 않는 파티 (0) | 2023.12.19 |