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을 출력한다.
코드
처음에 틀렸던 코드
n, m = map(int, input().split())
friend = [[] for _ in range(n)]
for _ in range(m):
a, b = map(int, input().split())
friend[a].append(b)
friend[b].append(a)
def dfs(node, cnt, visited):
if cnt >= 5:
print(1)
exit()
visited[node] = True
for nx in friend[node]:
if not visited[nx]:
dfs(nx, cnt+1, visited)
for i in range(n):
dfs(i, 1, [False] * n)
print(0)
생각해보니 위 코드는 사이클이 발생해서 시작노드로 돌아온 경우도 cnt가 5가 되어서 때문에 틀린 것 같다.
그래서 아래와 같이 고쳤더니 통과했다.
n, m = map(int, input().split())
friend = [[] for _ in range(n)]
for _ in range(m):
a, b = map(int, input().split())
friend[a].append(b)
friend[b].append(a)
def dfs(node, cnt, visited):
visited.add(node)
if len(visited) == 5:
print(1)
exit()
for nx in friend[node]:
if nx not in visited:
dfs(nx, cnt+1, set(visited))
for i in range(n):
dfs(i, 1, set())
print(0)
친구 관계가 4다리 건너서까지 있는지 없는지만 확인하면 되므로 set에 방문한 노드들을 넣어주어서 집합의 크기가 5가 되면 4다리 건너서까지 있다는 말이므로 1을 출력하고 프로그램을 종료시킨다.
'문제풀이 > DFS_BFS' 카테고리의 다른 글
[Python/파이썬] 백준 14940번 쉬운 최단거리 (0) | 2023.06.21 |
---|---|
[Python/파이썬] 백준 1600번 말이 되고픈 원숭이 (0) | 2023.06.19 |
[Python/파이썬] 백준 2668번 숫자고르기 (0) | 2023.04.25 |
[Python/파이썬] 백준 17836번 공주님을 구해라! (0) | 2023.04.24 |
[Python/파이썬] 백준 16234번 인구 이동 (0) | 2023.03.02 |