[백준] ABCDE

문제

https://www.acmicpc.net/problem/13023

13023번: ABCDE

문제
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개의 노드가 연결되어 있으면 됨!!