1️⃣ 서론
백준 문제 13023번 ABCDE 입니다. 파이썬(Python)으로 풀었습니다.
2️⃣ 문제 설명
- A는 B와 친구다.
- B는 C와 친구다.
- C는 D와 친구다.
- D는 E와 친구다. 다음의 조건을 만족하는지를 출력하는 문제입니다.
3️⃣ 풀이
위의 조건을 만족하려면 해당 그래프의 깊이가 5임을 증명하면 됩니다.
그 이유는 A->B->C->D->E 로 5개의 노드가 연결되어 있으면 되기 때문입니다.
이는 dfs나 bfs로 해결할 수 있으나 저는 dfs로 해결하였습니다.
그럼 소스코드를 보시겠습니다.
4️⃣ 소스코드
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
import sys
n, m = map(int, input().split())
arr = [[] for i in range(n)]
visited = [False] * n
# 그래프를 인접 리스트 방식으로 표현하였습니다.
for _ in range(m):
a, b = map(int, sys.stdin.readline().rstrip().split())
arr[a].append(b)
arr[b].append(a)
def dfs(idx, number):
if number == 4:
print(1)
exit()
for i in arr[idx]:
if not visited[i]:
visited[i] = True
dfs(i, number + 1)
visited[i] = False
# 노드를 순서대로 방문하며 dfs를 수행합니다.
for i in range(n):
visited[i] = True
dfs(i, 0)
visited[i] = False
print(0)
5️⃣ 마치며..
질문과 지적은 환영합니다. 이 문제는 최적의 정답일 수도 아닐수도 있습니다.
궁금한게 있으시면 아래 댓글 남겨주세요.🙏
댓글은 저에게 큰 힘이 됩니다!
감사합니다. ❤️
