14) 백준 13023 - ABCDE

13023번: ABCDE (acmicpc.net)

13023번: ABCDE

---

#include <bits/stdc++.h>

using namespace std;

int fri[2000];
int check[2000];
int answer;

vector<vector<int> > con;

void backtracking(int people, int cnt) {
	if(cnt == 5) {
		answer = 1;
		return;
	}
	check[people] = 1;
	for(int i = 0; i < con[people].size(); i++) {
		if(check[con[people][i]] == 0) {
			backtracking(con[people][i], cnt+1);
		}
	}
	check[people] = 0;
}

int main(void) {
	fill_n(fri, 2000, 0);
	vector<vector<int> > fri(2000);
	con = fri;
	fri.erase(fri.begin(), fri.end());
	
	int N, M;
	cin >> N >> M;
	
	int a, b;
	for(int i = 0; i < M; i++) {
		cin >> a >> b;
		con[a].push_back(b);
		con[b].push_back(a);
	}
	
	answer = 0;
	
	for(int i = 0; i < N; i++) {
		int cnt = 1;
		backtracking(i, cnt);
		if(answer == 1) {
			cout << "1";
			break;
		}
	}
	if(answer == 0) {
		cout << "0";
	}
}

문제는 백트래킹 / DFS로 풀면 되는 문제 같다.

 

친구 관계는 con 2차 벡터에 넣어줬다.

 

check를 통해 연결된 친구를 확인해서 한번 체크 한 친구를 또 체크 안 하도록 했다.

예를 들어 1과 2가 친구,  2와 3이 친구, 3과 4 친구, 1과 3이 친구일 경우 1 - 2 - 3 - 4를 체크하면 되지만 1 - 2 - 3 - 1로 되는 경우를 방지함이랄까...!!!  친구가 안 됐을 경우 check를 다시 0으로 바꿔주었다.

 

cnt로 연결된 친구가 5이 될 경우 1 출력후 프로그램 종료.

 

2년전에 푼 문제였는데 이번엔 성공했다. 기분이 좋다. 흐흐흐ㅡㅎ