[백준13023] ABCDE

문제

---

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

13023번: ABCDE

 

생각의 흐름

---

전형적인 DFS 문제이다. 문제의 요점은 A-B, B-C, C-D, D-E인 친구관계가 존재하는지를 조사하는 것이다. adjacent list를 이용하여 연결관계에 대한 정보를 저장하고 시작점을 vertex 0부터 n-1까지 돌아가면서 dfs를 사용하여 depth가 4이상이 되는 subgraph가 존재하는지를 판별하면 된다.

 

코드

---

n, m = map(int, input().split())
adj_lst = [[] for i in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    adj_lst[a].append(b)
    adj_lst[b].append(a)

visited = [False for i in range(n)]

def dfs(v, depth):
    global ans
    visited[v] = True
    if depth == 4:
        ans = True
        return
    for nxt in adj_lst[v]:
        if not visited[nxt]:
            dfs(nxt, depth+1)
            visited[nxt] = False

ans = False
# 돌아가면서 dfs의 시작점 설정
for i in range(n):
    dfs(i,0)
    visited[i] = False
    if ans:
        break
print(1 if ans else 0)