13023. [Python]ABCDE

1. 문제

 

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

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 512MB
• 백트래킹

 

3. 파이썬 코드

 

import sys
# 백트래킹
def DFS(s,depth):
    # 최대 연결된 인원이 5명인 경우 1을 출력 후 탈출
    if depth == 5:
        print(1)
        exit()
    # 연결된 인원들 탐색하며 백트래킹
    for j in matrix[s]:
        if visited[j] == False:
            visited[j] = True
            DFS(j,depth+1)
            visited[j] = False

input = sys.stdin.readline

N, M = map(int,input().split())

matrix = [[] for _ in range(N)]
# 양방향 그래프 구성
for _ in range(M):
    start, end = map(int,input().split())
    matrix[start].append(end)
    matrix[end].append(start)
# 0번 사람부터 N-1 번 사람까지 탐색해가며 연결 깊이 체크
for i in range(N):
    visited = [False] * N
    visited[i] = True
    DFS(i,1)
else:
    print(0)

 

4. 문제를 풀고난 후 생각

 

• 문제를 읽어본 후 요구하는 조건을 해석하는 부분이 조금 오래 걸렸던 문제였다.
• 결국 문제에서 요구하는 것은 깊이가 5 이상이 존재하는지 여부를 묻는 문제였고, 단순히 DFS로 구현을 진행했는데 틀렸다.
• 그 이유는 노드를 방문하는 순서에 따라서 깊이가 5가 될 수 있고 안되고 차이가 존재했기 때문이였고, 이를 바탕으로 백트래킹으로 코드를 다시 구현하여 문제를 해결하였다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 백트래킹