[문과 코린이의 IT 기록장] C++ 백준 문제풀이[그래프 1] - ABCDE (13023)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[그래프 1] - ABCDE (13023)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[그래프 1] - ABCDE (13023)

 

---

 

13023번: ABCDE

[ 문제 ]

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을 출력한다.

---

[ 코드 ]

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

bool a[2000][2000]; // 인접 배열로 그래프의 정보를 저장하는 2차원 배열 (i,j가 간선이 존재하면 1, 존재하지 않으면 0)

vector <int> g[2000]; // E를 쉽게 찾기위한 배열
// vector <int> v(n) : n의 크기만큼 배열을 생성하며, 동시에 각 배열의 값을 0으로 초기화한다. (입력은 직접, push_back모두 가능)
// vector <int> v[n] : 사용자가 앞으로 입력하게 되는 갯수 만큼의 2차원 배열이 생성된다. (입력은 push_back 활용)

vector <pair<int, int>> edges; // 간선 저장
// pair<type, type> : 2개의 각각 지정한 타입을 저장하며, 저장한 값은 .first, .second로 각각 접근 가능)
// 2개의 연관된 값에서, 각각의 조건에 따라 정렬한 결과를 얻고자 할 때 사용하면 좋다.


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;

		// E를 쉽게 찾게 하기위한 배열
		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;


			/* A,B,C,D 정점이 모두 겹치지 않는 간선을 찾음. */
			if (A == B || A == C || A == D || B == C || B == D || C == D)
			{
				continue;
			}


			/* 이제 선택된 정점들의 B -> C의 친구관계가 조건에 맞는지 확인  */
			// B -> C
			if (!a[B][C]) // 관계가 false가 아니면
			{
				continue;
			}

			/* A,B,C,D의 친구관계 형성. D와 친구관계가 존재하는 E를 찾기 (E는 앞의 정점들과 겹치면 안됨)*/
			// D -> E
			for (int E : g[D]) { // D와 연결되어있었던 것들 중 E를 찾기
				if (A == E || B == E || C == E || D == E)
				{
					continue;
				}
				cout << 1 << '\n';
				return 0;
			}

		}
	}


	cout << 0 << '\n';
	return 0;
}