DFS(깊이 우선 탐색): 백준 13023 파이썬

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

13023번: ABCDE

 

풀이:

이 문제는 bfs를 사용해 친구관계의 깊이가 4라면 1을 출력하고 4의 깊이까지 도달하지 못한다면 0을 

출력하면 된다.

 

이 문제에서 어려웠던 점은 백트레킹을 고려해야 한다는 것이다.

백트레킹을 하지않는다면 선택된 노드에 따라 탐색할 수 있는 깊이가 달라지기 때문에 정답이 될 수 없다.

 

정답:

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
visited = [False] * n

# 입력받은 그래프 정보를 인접 리스트 방식으로 저장
for _ in range(m):
    a, b = map(int, input().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)


def dfs(v, depth):
    if depth == 4:
        print(1)
        exit()
    for i in graph[v]:
        if not visited[i]:
            # 현재 노드를 방문처리
            visited[i] = True
            dfs(i, depth+1)
            # 백트레킹을 위해 방문처리를 해제
            visited[i] = False


# dfs 수행
for i in range(n):
    visited[i] = True
    dfs(i, 0)
    visited[i] = False

print(0)