[백준 11562번] 백양로 브레이크 C++ 풀이/해결

백양로 브레이크 성공

---

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	2246	1157	864	49.400%

 

문제

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

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

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

 

---

풀이

#include<iostream>

using namespace std;

int n,m;//입력값



int road[251][251] = {0};

void FloydWarshall() {
	for (int via = 1; via <= n; via++) {
		for (int from = 1; from <= n; from++) {
			for (int to = 1; to <= n; to++) {		
				 if (road[from][to] > road[from][via] + road[via][to])
					road[from][to] = road[from][via] + road[via][to];
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	


	cin >> n >> m;

	for (int i = 1; i <=n; i++)
	{
		for (int j = 1; j <=n; j++)
		{
			road[i][j] = 1000000000;

		}
	}


	int u, v, b;
	for (int i = 0; i < m; i++)
	{
		cin >> u >> v >> b;
		
		road[u][u] = 0;
		road[v][v] = 0;

		road[u][v] = 0;
		if (b == 0)
		{
			road[v][u] = 1;
		}
		else 
		{
			road[v][u] = 0;
		}
			
	}



	FloydWarshall();

	int k;
	cin >> k;
	int s, e;
	for (int i = 0; i < k; i++)
	{
		cin >> s >> e;
		cout << road[s][e]<<'\n';
	}
}

 

정답비율 낮추는데 제일 많이 기여했을듯한 1등공신의 화면입니다.

 

처음에는 못풀어서 다른 사람이 어떻게 풀었는지 코드를 안보고 대충 도입부에 말만 보고 코드를 풀어놓았는데 어쩌다보니 정답비율 낮추는데에 큰 공헌을 했습니다.

 

처음에는 시간초과라서 

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

 

이렇게 3줄을 넣어주니 그다음부터는 다행히 시간초과는 뜨지않지만 계속 틀렸습니다의 연속 퍼레이드라서 다른 사람들은 도대체 어떻게 풀었는지 코드를 볼 수 밖에 없었습니다.

 

근데 다른 사람들의 코드를 봐도 풀이과정이 똑같았고 진짜 진짜 너무 똑같아서 백준은 나만 왕따시키는게 혹시 아닐까 생각을 했지만 마침내 발견했습니다.

 

진짜진짜 왕왕왕 짜증났다!!!

요  road[v][v] =0자식 이 자식 때문에 틀렸습니다. 사실 제가 멍청멍청하게 road[u][u] =0 만을 해준게 잘못이긴하지만 저 자식이 너무 교묘하게 숨어있는게 나빳자나여 

 

다른 사람들의 코드를 보다보니 괜히 입력부에서 0을 해준것같기도 합니다. 너무 좁게만 보고있었기에 반성해야겠습니다.

 

 

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

11562번: 백양로 브레이크