[백준] 13023 ABCDE

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

그래프에서 계속해서 다음 깊이를 탐색하는 것으로 깊이가 5가 되는 관계가 있는지 탐색이 필요했습니다.

DFS를 재귀로 구현하여 ABCDE 관계가 있는지 여부를 탐색하였습니다.

2) 알고리즘

• DFS
• 재귀

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

def solution(node, ans):            # 현재 사람 번호, 탐색 깊이
    global answer

    if ans >= 5:                    # ABCDE 관계가 된다면
        answer = True               # 정답 변경
        return

    visited[node] = 1               # 현재 사람 탐색 체크

    for next in linked[node]:       # 현재 사람과 친구인 사람들 탐색
        if not visited[next]:       
            solution(next, ans+1)   # 아직 탐색하지 않은 사람이면, 다음 단계 탐색
    
    visited[node] = 0               # 현재 사람 탐색 해제

N, M = map(int, sys.stdin.readline().split())       # 사람, 친구 관계 수
linked = [[] for _ in range(N)]                     # 사람간 친구 관계
visited = [0] * N                                   # 탐색 여부
answer = False                                      # ABCDE 존재 여부

for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    linked[a].append(b)                             # 친구 관계 연결
    linked[b].append(a)

for k in range(N):              # 0번부터 탐색
    solution(k, 1)

    if answer:                  # ABCDE 관계가 있다면
        print(1)                # 1 출력
        break
else:                           # 관계가 없다면, 0 출력
    print(0)

---

🔗 문제 링크

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

13023번: ABCDE

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다