문제
https://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와 친구다.
위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.
예제 입력 1
5 4
0 1
1 2
2 3
3 4
s
예제 출력 1
1
풀이
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
n, m = map(int, input().split())
arrive = False
a = [[] for _ in range(n+1)]
visited = [False]*(n+1)
def dfs(now,depth):
global arrive
if depth == 5:
arrive = True
return
# 방문 리스트에 현재 노드 방문 기록 저장
visited[now] = True
# 방문 노드의 연결 노드 중 방문하지 않은 노드로 DFS 실행
for i in a[now]:
if not visited[i]:
dfs(i, depth+1)
visited[now] = False
for _ in range(m):
s,e = map(int, input().split())
a[s].append(e)
a[e].append(s)
for i in range(n):
# 노드마다 dfs 실행
dfs(i, 1)
if arrive:
break
if arrive:
print(1)
else:
print(0)

설명
인접 리스트로 저장하는거 까지는 이해가 됐었는데 이후 dfs 를 어떤식으로 접근해야하는지 아직도 잘 안됐다...ㅠ.ㅠ.ㅠ...
++ 발생했던 오류 중 런타임 에러 (IndexError) 해결 방법
- 방문 기록을 저장하는 리스트인 visited 선언 시 [] 가 한번 더 들어갔었다.
- 노드마다 dfs 실행 시 인덱스 설정을 똑바로 해줘야 한다.
그래프 데이터를 저장하는 인접 리스트인 a 와 방문 기록을 저장하는 리스트인 visited 를 n+1 만큼 설정해줬다.
이는 초기 실행하는 dfs의 depth 값을 1부터 시작하기 위함이다!
모르겠어서 인터넷을 참고하면서 해봤는데, 중간에 왜 깊이가 5일때까지만 검사하는지가 이해되지 않았었다.
-> 문제에서 위와 같은 친구 관계가 존재하는지 여부를 구하라고 했음. A -> B -> C -> D -> E 로 5개의 노드가 연결되어 있으면 됨!!
'Coding Test > Python' 카테고리의 다른 글
| [백준] 9095 - 1, 2, 3 더하기 (0) | 2023.09.13 |
|---|---|
| [백준] 2609 - 최대공약수와 최소공배수 (0) | 2023.09.11 |
| [프로그래머스] 여행경로 (lv.3) (0) | 2023.08.28 |
| [프로그래머스] 아이템 줍기 (lv.3) (0) | 2023.08.24 |
| [프로그래머스] 단어 변환 (lv.3) (0) | 2023.08.16 |