728x90
문제 링크 : www.acmicpc.net/problem/13023
13023번: ABCDE
문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.
www.acmicpc.net
문제
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을 출력한다.
접근 방법
문제에서 아래의 조건이 주어졌다.
- A는 B와 친구다.
- B는 C와 친구다.
- C는 D와 친구다.
- D는 E와 친구다.
이는 N명에게 연결된 친구를 각각 dfs 로 타고 가봤을 때, 그 깊이가 4가 되는게 있는지를 확인해서 풀 수 있다.
벡터 배열을 이용해 양방향으로 친구 관계를 연결해주고 벡터 배열 크기만큼 dfs를 돌린다.
첫번째와 두번째 방법은 같으나
첫번째는 flag 변수와 return; 으로 dfs를 중단해보았고
두번째는 exit(0); 으로 즉시 종료를 해보았다.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int visited[2000] = {0};
vector<int> vecArr[2000];
bool flag = false;
void dfs(int start, int depth){
visited[start] = 1;
if(depth==4){
flag = true; //더 이상 dfs 실행 안 되게 함.
cout << 1 << "\n";
return;
}
for(int i = 0; i<vecArr[start].size(); i++){
if(visited[vecArr[start][i]]==0 && !flag){ //위에서 flag=true 됐으면 조건문 실행 x
dfs(vecArr[start][i], depth+1); //타고 들어갈 때마다 depth 증가
}
}
visited[start] = 0;
}
int main(){
queue<int> que;
int N,M;
cin >> N >> M;
int a, b;
for(int i = 0; i<M; i++){ //관계 양 방향 연결 (벡터 배열 사용)
cin >> a >> b;
vecArr[a].push_back(b);
vecArr[b].push_back(a);
}
for(int i = 0; i<N; i++){
dfs(i,0);
}
if(!flag) cout << 0; //다 탐색 했는데 깊이가 4 된 경우 없으면 0 출력.
return 0;
}
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int visited[2000] = {0};
vector<int> vecArr[2000];
void dfs(int start, int depth){
visited[start] = 1;
if(depth==4){
cout << 1 << "\n";
exit(0); //즉시 종료.
}
for(int i = 0; i<vecArr[start].size(); i++){
if(visited[vecArr[start][i]]==0){
dfs(vecArr[start][i], depth+1);
}
}
visited[start] = 0;
}
int main(){
queue<int> que;
int N,M;
cin >> N >> M;
int a, b;
for(int i = 0; i<M; i++){
cin >> a >> b;
vecArr[a].push_back(b);
vecArr[b].push_back(a);
}
for(int i = 0; i<N; i++){
dfs(i,0);
}
cout << 0; //dfs()에서 즉시 종료 했으므로 depth==4가 있는 경우 해당 코드 실행 x.
return 0;
}
728x90
'Algorithm(BOJ) > DFS' 카테고리의 다른 글
| [C++] 백준 1759번 - 암호 만들기 (DFS) (0) | 2021.03.07 |
|---|---|
| [C++] 백준 2667번 - 단지 붙이기 (DFS) (0) | 2021.03.03 |
| [C++]백준 7562번 - 나이트의 이동 (0) | 2021.01.14 |
| [C++]백준 1389번 - 케빈 베이컨의 6단계 법칙 (0) | 2021.01.14 |
| [C++]백준 2644번 - 촌수계산 (BFS) (0) | 2021.01.13 |
