일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 |
Tags
- 독일어독학
- 카카오인턴십
- istringstream
- dp
- 롯데정보통신
- 리눅스
- 부주상골수술
- BFS
- DFS
- IOS
- 세브란스
- 부주상골수술후기
- 구현
- c++
- 카카오인턴
- 독학
- 프로그래머스
- sql
- 코테
- 스택
- 카카오코테
- 독일어
- SQLD
- 부주상골
- SWIFT
- 분할정복
- ChatGPT
- 코딩테스트
- 백준
- 부주상골증후군
Archives
- Today
- Total
슈뢰딩거의 고등어
[백준] 17089 세친구 본문
https://www.acmicpc.net/problem/17089
17089번: 세 친구
첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 의미하는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, 그리고 B와 A가 친
www.acmicpc.net
#include <iostream>
#include <vector>
using namespace std;
int n, m;
int answer = 987654321;
int arr[4010];
vector <int> friends[5000];
bool visit[5000];
int choice[5];
// new_no 가 choice 들과 친구인지 확인
bool checker(int cnt, int new_no) {
if(cnt == 0)
return true;
int relations = 0;
for(int i=0; i<friends[new_no].size(); i++) {
int target = friends[new_no][i];
if(cnt == 1) {
if(target == choice[0])
return true;
}
else if(cnt == 2) {
if(target == choice[0])
relations++;
else if(target == choice[1])
relations++;
if(relations >= 2)
return true;
}
}
return false;
}
void dfs(int idx, int cnt, int target) {
if(cnt == target) {
int total = 0;
for(int i=0; i<target; i++) {
int no = choice[i];
total += friends[no].size();
}
total -= 6;
if(answer > total && total >= 0)
answer = total;
return;
}
for(int i=idx; i<=n; i++) {
if(visit[i] == true) continue;
if(checker(cnt, i) == false)
continue;
visit[i] = true;
choice[cnt] = i;
dfs(i, cnt+1, target);
visit[i] = false;
}
}
int main() {
scanf("%d %d", &n, &m);
for(int i=0; i<m; i++) {
int a, b;
scanf("%d %d", &a, &b);
friends[a].push_back(b);
friends[b].push_back(a);
}
dfs(1, 0, 3);
if(answer == 987654321)
printf("-1");
else
printf("%d\n", answer);
}
시간을 줄이기 위해서 새로운 노드를 추가하기 전에 친구관계가 맞는지 검증을 한다.
모두가 친구여야하는 조건이기 때문에
a의 친구수+ b의 친구수 + c 의 친구수 - 6
을 해주면 원하는 답이 나온다.
'알고리즘' 카테고리의 다른 글
[백준] 17085 십자가 2개 놓기 (0) | 2022.01.27 |
---|---|
[백준] 17406 배열 돌리기 4 (0) | 2022.01.25 |
[백준] 2422 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (0) | 2022.01.24 |
[백준] 2210 숫자판 점프 (0) | 2022.01.24 |
[백준] 16943 숫자재배치 (0) | 2022.01.24 |
Comments