문제:
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을 출력한다.
풀이방법:
처음에는 문제를 조금 이해하는 것이 어려웠다. 주어진 모든 사람의 관계가 조건과 같이 구성되어야 하는줄 알았는데, 일부 사람들만 관계를 유지하면 된다. 따라서 N명의 사람들의 관계를 트리 형태로 구성했을 때, 하나의 노드로부터 깊이가 4인 경우가 있는지 확인하면 된다.
따라서 처음에는 주어진 관계들을 양방향 그래프로 정리를 한다. 그 다음에는 각 노드로부터 dfs를 수행했을 때, 깊이가 4인 경우가 있는지 확인한다. 깊이가 4인 경우가 한 개라도 있으면 되기 때문에 찾았다면 탐색을 중지하고 1을 출력하며, 모든 노드로부터 탐색했는데 없다면 0을 출력하도록 한다.
|
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
|
def dfs(node, depth):
global answer
if depth==4:
answer = 1
return
for f in friends[node]:
if f in relationship:
continue
relationship.append(f)
dfs(f,depth+1)
relationship.pop()
N, M = map(int,input().split())
friends = [[] for _ in range(N)]
for _ in range(M):
a, b = map(int, input().split())
friends[a].append(b)
friends[b].append(a)
answer = 0
for i in range(N):
relationship = [i]
dfs(i, 0)
if answer:
break
print(answer)
|
cs |
문제링크:
https://www.acmicpc.net/problem/13023
13023번: ABCDE
문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.
www.acmicpc.net
'Algorithm > Python' 카테고리의 다른 글
| [BOJ] 2251. 물통 (0) | 2021.10.28 |
|---|---|
| [BOJ] 15988. 1, 2, 3 더하기 (0) | 2021.10.25 |
| [BOJ]1339. 단어 수학 (0) | 2021.10.21 |
| [BOJ] 15658. 연산자 끼워넣기 (2) (0) | 2021.10.20 |
| [BOJ] 17140. 이차원 배열과 연산 (0) | 2021.10.19 |