[알고리즘][백준 13023] ABCDE

문제 링크

백준 13023 ABCDE문제 링크

문제 풀이

A = B
B = C
C = D
D = E와같이 친구 관계가 연결되어있으면 1, 그렇지 않다면 0을 출력한다.

입력받은 사람을 A~X라고 하자.
graph라는 리스트를 만드는데, x번째 행에는 x와 친구관계에 있는 사람들이 누구인지에 대한 정보가 담겨있다.
그리고 bool형 리스트 visit를 만든다.
먼저 DFS를 A~X까지 다 돈다.

DFS에서 해당 인덱스의 graph를 확인한다. (graph[인덱스])
다음, 해당 graph[인덱스]에 친구관계이고, 아직 방문을 안한 곳(visit = False)에서 다시 DFS를 실행한다. 이 때, 깊이(myDepth)를 1 증가 시켜준다.
이렇게 DFS를 계속 진행하다가, myDepth가 4이상이 된다면, 해당 조건(A = B, B = C, C = D, D = E)를 만족하는 것이어서 1을 출력한다.
아니면 0을 출력한다.
(visit 리스트는 위의 밑줄친 반복문(for문)을 돌때마다 전부 false가 되어있어야 한다. )

내 코드

import sys

n, m = map(int, sys.stdin.readline().split())
graph = [[] for i in range(n+1)]
visit = [False for i in range(n + 1)]

visit[0] = True

for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a+1].append(b+1)
    graph[b+1].append(a+1)

def dfs(graph, i, myDepth):
    global ans
    visit[i] = True
    
    if myDepth >= 4:
        ans = True
        return
    for j in graph[i]:
        if visit[j] == False:
            dfs(graph, j, (myDepth+1))
            visit[j] = False
        
        

ans = False
for i in range(1, n+1, 1):
    dfs(graph, i, 0)
    visit[i] = False
    if ans:
        break

print(1 if ans else 0)