백준[ 13023 | Python ] ABCDE

문제

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

풀이

문제에서의 중요한 조건은 다음과 같다.

- A, B, C, D, E는 연속적인 친구 관계이다.
- A가 B와 친구이면 B와 A가 친구인 것과 같다.  

이 두 조건을 염두에 두고 접근했다.
먼저 친구관계정보를 그래프로 만들어주고 DFS로 탐색한다.

탐색을 할 때 연속적인 친구 관계를 계산하기 위해 현재 탐색하고 있는 depth에 1을 더해 다음 탐색에 전해준다.

A~E가 연속적인 친구 관계를 맺는다는 것은 DFS를 통한 탐색의 층이 5층까지 이루어졌다는 의미와 같기 때문에 depth가 5인 탐색이 있다면 1을 출력한다.

처음 탐색을 수행할 때의 층은 1층이어야 5층까지 진행된다.(0층 부터 4층까지어도 상관없다.)

import sys
input = sys.stdin.readline
n, m = map(int,input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

def dfs(start,depth):
    if depth >= 5:
        print(1)
        exit(0)
    for i in graph[start]:
        if not v[i]:
            v[i] = 1
            dfs(i, depth+1)
            v[i] = 0
    
for i in range(n):
    v = [0]*n
    v[i] = 1
    dfs(i,1)
    v[i] = 0
print(0)

생각 & 정리

문제를 읽고는 확연히 DFS문제임을 알 수 있는 모범적인 문제였다.
연속적인 과 같은 키워드는 DFS로 해결해야함에 더 가까운 의미인 것 같다.