[baekjoon] 백준 13023번(파이썬): ABCDE

문제

13023번: ABCDE

알고리즘

- dfs 탐색을 통해 문제를 수행한다.

- 반복문을 통해 각 친구들의 친구 관계를 확인한다.

- 친구 관계는 백 트래킹을 통해 확인하고 친구 관계를 확인할 때마다 깊이를 +1 해준다.

- 친구 관계의 깊이가 4라면 문제에서 원하는 친구 관계이므로 1을 출력하고 시스템을 종료한다.

- 문제에서 원하는 친구 관계가 아니면 0을 출력한다.

코드

import sys


# dfs 탐색
def dfs(v, depth):

    # 친구 관계가 존재한다면 1출력 후 종료
    if depth == 4:
        print(1)
        exit()

    # 반복문을 통해 친구 관계 확인
    for j in graph[v]:
        # 탐색하지 않은 친구라면
        if not visited[j]:
            visited[j] = True
            dfs(j, depth + 1) # 백 트래킹을 통해 깊이 확인
            visited[j] = False


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

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

# 반복문을 통해 각 친구들의 친구관계를 확인
for i in range(n):
    visited[i] = True
    dfs(i, 0)
    visited[i] = False

# 친구 관계가 존재하지 않으므로 0 출력
print(0)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법