백준 문제풀이/GRAPH

[Graph] BOJ 13023 : ABCDE

준코딩 2019. 7. 18. 08:52
백준 알고리즘 강의를 토대로 작성된 문제풀이입니다.

문제

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

  • A는 B와 친구다.

  • B는 C와 친구다.

  • C는 D와 친구다.

  • D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

 

출력

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

풀이

 

문제를 한마디로 정리해보자면

" 다섯명의 꼬리를 무는 관계를 찾아라. "

라고 할 수 있다.

 

 

간단해 보이지만 입력부터 많은 생각을 고려할 필요가 있다.

우선 3개의 배열을 만든다.

 

 

1. 인접배열로 그래프의 정보를 저장하는 2차원 배열

2. 모든 간선을 저장할 배열

3. 마지막 E 의 관계를 찾기위한 배열

(3번 배열을 만든 이유는 마지막에 설명)

 

 

배열을 모두 선언하고 for 문을 통해서 입력을 받을건데

A 와 B 가 친구라면 A -> B 도 성립되고

B -> A 도 성립된다. 

 

 

따라서 이 그래프는 무방향 그래프가 될것이고

간선을 입력할때 두 방향 모두 입력할 필요가있다.

 

 

입력이 모두 끝나면 모든 간선을 돌면서 연속적인 친구관계를 찾아야 한다.

무방향 그래프로 인해서 간선의 개수가 두배가 되었기 때문에

입력된 간선의 두배만큼 탐색을한다.

 

 

가장 처음에 i 와 j 번째의 간선 관계를 확인한다.

이때 선택된 간선의 정점이 한개도 겹치지 않는 두 간선을 찾는다!!.

 

 

그렇게 되면 사람 A,B,C,D 가 나올것이고

필연적으로 A - B , C - D 두개의 친구 관계가 생긴다.

 

 

여기서 우리는 B - C 의 관계만 확인해주면 4개의 연속적인 관계를 확인할 수 있다.

이 정보는 미리 저장해두었던 인접그래프에서 찾을 수 있다.

 

 

자, 여기까지 2개의 배열을 사용해서 4개의 연속적인 관계를 확인했다.

이제 마지막 5번째 친구만 확인하면 된다.

이건 간단한게 D 의 친구가 앞에서 정해진 A,B,C 만 아니면 된다.

 

 

이때 우리는 3번째 배열을 사용해서 간단하게 찾을 수 있다.

3번째 배열은 마치 인접리스트와 느낌이 비슷하기 때문에

한 정점에 대한 간선을 쉽게 찾을 수 있다.

 

이렇게 모든 조건이 성립되는 관계가 존제할때 1을 출력한다.

 

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool a[2000][2000]; // 그래프
vector<int> g[2000]; //E 를 쉽게 찾기위한 배열
vector<pair<int, int>> edges; //간선

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int from, to;
		cin >> from >> to;
		edges.push_back({ from, to }); //무방향 그래프
		edges.push_back({ to, from });
		a[from][to] = a[to][from] = true;
		g[from].push_back(to);
		g[to].push_back(from);
	}
	m *= 2; //관계하나에 간선이 두개씩 추가됨
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < m; j++) {
			// A -> B
			int A = edges[i].first;
			int B = edges[i].second;
			// C -> D
			int C = edges[j].first;
			int D = edges[j].second;
			if (A == B || A == C || A == D || B == C || B == D || C == D) {
				continue;
			}
			// B -> C
			if (!a[B][C]) {
				continue;
			}
			// D -> E
			for (int E : g[D]) {
				
				if (A == E || B == E || C == E || D == E) {
					continue;
				}
				cout << 1 << '\n';
				return 0;
			}
		}
	}
	cout << 0 << '\n';
	return 0;
}