백준13023 - ABCDE

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

13023번: ABCDE

주어진 숫자들 중에서 친구관계 4개를 찾으면 1을 출력하고 못 찾을 경우 0을 출력하는 문제다. 나는 DFS를 사용하여 풀었다.

 

길찾기와 다르게 모든 경로를 탐색하지 않고 친구관계 4개만 빠르게 찾으면 되는 문제이기 때문에 DFS를 이용하여 깊이가 4인 경우를 찾았다.

 

이차원 벡터를 이용하여 친구관계를 표현하였다. 이차원 배열을 사용할 수도 있었는 데 기업 코딩테스트에서 이차원 백터를 주어지고 문제를 풀라는 경우가 많아서 이차원 백터를 사용해 보았다.

 

#include <iostream>
#include <vector>
#define MAX 2000
using namespace std;

bool visit[MAX] = { false, }; //친구 방문 여부
vector<int> v[MAX]; //친구 관계

void dfs(int x, int idx) { //친구 x, idx개의 친구 관계
	visit[x] = true; //친구 x를 방문처리
	if (idx == 4) { //4개를 찾기만 하면
		cout << 1; //1 출력하고
		exit(0); //종료
	}
	for (int i = 0; i < v[x].size(); i++) { //x에 대한 친구관계를 모두 조사
		if (!visit[v[x][i]]) { //방문하지 않은 친구면
			dfs(v[x][i], idx + 1); //그 친구부터 다시 탐색
		}
	}
	visit[x] = false; //현재 x를 미방문처리
}

int main() {
	int n, m;
	int a, b;
	cin >> n >> m;
	
	for (int i = 0; i < m; i++) {
		cin >> a >> b;

		//친구니까 서로 관계를 맺어준다.
		v[a].push_back(b);
		v[b].push_back(a);
	}

	//n명에 대하여 dfs를 수행하여 깊이가 4가 되는 경우를 찾는다.
	for (int i = 0; i < n; i++) {
		dfs(i, 0);
	}

	cout << 0; //못 찾은 경우는 0을 출력
}