[Python] 백준 풀기 13023 - ABCDE

파이썬 백준 13023번

골드5

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

13023번: ABCDE

 

 

 

 

 

문제 보기

분류: 그래프 탐색, 깊이 우선 탐색

 

 

 

 

 

문제 풀기

사람 다섯명이 연속적으로 주루룩 4번 이상의 연결이 형성되면 문제에서 제시한 관계가 만족한다. 맞으면 1, 아니면 0.

 

 

주어진 입력을 graph (relationships) 로 저장하여 모든 사람에 대해 연속 4번의 관계가 만족하는지 모두 탐색해 본다.

이때, DFS 가 재귀함수로 4번이 실행되면 fnDFS 를 result == True 로 나와 관계를 만족하여 1 을 출력하고, 그렇지 않고 4번의 재귀가 일어나지 않으면 0 을 출력한다.

 

 

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline

## 사람 x 에 대해 관계의 수 depth 를 fnDFS 에서 받음.
def fnDFS(depth, x):
    global result
    ## 5명이 4번의 관계 이상을 갖는다면 result = True 표시하고 탈출.
    if depth == 4:
        result = True
        return
    
    ## 한 사람(노드)을 선택하여 그 사람과 관계가 있는 모두를 탐색.
    for i in relationships[x]:
        ## 방문하지 않았으면 방문표시를 하고 depth + 1, 다음 i 에 대해 fnDFS 진입. 그리고 현재 방문 위치는 초기화.
        if not visited[i]:
            visited[i] = True
            fnDFS(depth + 1, i)
            visited[i] = False


if __name__ == "__main__":
    ## N, M 입력.
    N, M = map(int, inputdata().split())
    
    ## 친구 관계를 저장할 relationships, 방문을 표시할 visited 그리고 결과를 False 로 초기화.
    relationships = [[] for _ in range(N)]
    visited = [False] * N
    result = False
    
    ## 친구 관계를 relationships 에 index 에 맞게 서로 저장
    for _ in range(M):
        a, b = map(int, inputdata().split())
        relationships[a].append(b)
        relationships[b].append(a)
    print(relationships)           # test print
    
    
    ## 입력 받은 데이터를 가지고 관계의 수만큼 반복문을 돌린다.
    for x in range(N):
        ## 방문 표시를 하고 fnDFS 를 진입.
        visited[x] = True
        fnDFS(0, x)
        ## 방문 표시를 초기화하여 다음 사람(노드)를 준비. 만약 result == True 면 break.
        visited[x] = False
        if result:
            break
    
    if result:
        print(1)
    else:
        print(0)



# 8 8
# 1 7
# 3 7
# 4 7
# 3 4
# 4 6
# 3 5
# 0 4
# 2 7

# [[4], [7], [7], [7, 4, 5], [7, 3, 6, 0], [3], [4], [1, 3, 4, 2]]

# 1