[백준 13023] ABCDE

문제출처 : https://www.acmicpc.net/problem/13023

 

A → B → C → D → E 의 관계가 성립하는 그래프가 있는지 확인하는 문제 입니다.

깊이 우선 탐색을 이용하여 4단계까지 깊이가 생성된다면 1을 출력하고, 생성되지 않는다면 0을 출력하면 됩니다.

문제 이해하기

아래와 같은 친구 관계가 있습니다.

1번에서부터 친구 관계를 찾아보면 4단계의 깊이를 내려갈 수 없습니다. 2번에서 시작해도 마찬가지로 4단계의 깊이로 내려갈 수 없습니다. 4번이나 5번에서 시작해야만 4단계의 깊이로 내려갈 수 있습니다. 따라서 이 문제는 모든 친구를 A로 가정하고 다 확인해봐야 합니다.

코드작성

함정이 없고, 이해하기 쉽기 때문에 바로 코드를 작성하겠습니다.

입력 받기

mii = lambda : map(int, input().split())

N, M = mii()

arr = [[] * N for _ in range(N)]
for _ in range(M):
    u, v = mii()
    arr[u].append(v)
    arr[v].append(u)

사람의 수 N과 친구 관계 M을 입력 받습니다. 그리고 M개의 줄에는 두 친구의 관계 u, v를 입력 받아 연결을 시켜줍니다.

결과 확인

visited = [False] * N
chk = False
for i in range(N):
    dfs(i, 0)
   
    if chk:
        break

if chk:
    print(1)
else:
    print(0)

visited 리스트는 방문 여부를 판단하는 역할을 합니다. chk는 A부터 E까지 연결된 친구 관계가 있는지 파악하는 변수 입니다. 모든 친구를 다 파악하는 것이 아니라 연결 관계가 있는 친구가 나타나면 바로 break로 반복문을 종료합니다.

이제 모든 친구를 시작 위치라 생각하고 깊이가 4단계까지 들어가는 관계가 있는지 확인 합니다. dfs 함수에는 두개의 인자가 들어갑니다. 첫 인자는 시작 위치인 i가 들어가고, 두 번째 인자는 깊이를 확인하는 인자 입니다. 아직 깊이가 없기 때문에 0으로 시작합니다. dfs 함수는 아래에서 다시 작성하겠습니다.

모든 반복문을 종료 후 chk를 확인하여 True라면 1을 출력하고, 아니면 0을 출력하여 종료 합니다.

dfs 함수

def dfs(node, depth):
    global chk
    visited[node] = True

    if depth == 4:
        chk = True
        return

    for nxt_node in arr[node]:
        if visited[nxt_node]:
            continue
        dfs(nxt_node, depth + 1)
    
    visited[node] = False

dfs 함수 입니다. 매게 변수로 현재 노드와 깊이를 입력 받았습니다. 먼저 chk 변수를 전역변수로 선언 합니다. 하나라도 깊이가 4단계인 관계가 있으면 바로 끝을 내주기 위해서 입니다.

dfs 함수를 시작하면 바로 방문 표시를 해야합니다. 그렇기에 visited[node] 값을 True로 바꿔주었습니다. 다음으로 깊이가 4가 되었다면 chk 값을 True로 바꿔주고 종료시키는 로직을 추가하였습니다.

다음으로 현재 노드를 탐색하는 로직 입니다. 현재 노드에 연결된 다음 노드들을 확인하여 이미 방문했던 노드는 넘어가고 아직 방문하지 않은 노드들만 다시 dfs 함수를 실행합니다. 이 때 다음 노드를 방문할 때에는 깊이를 1 늘려주기 위해 depth + 1을 넣어주었습니다.

마지막으로 dfs 함수가 끝나면 방문 여부를 다시 원상복구 합니다. 매 친구마다 연결정보를 다시 만들어주어야 하기 때문에 백 트래킹처럼 관계를 다시 원상복구 시켜야 다음 친구 관계를 확인 할 수 있습니다.

전체 코드

전체 코드를 확인해 보겠습니다.

mii = lambda : map(int, input().split())
N, M = mii()

arr = [[] * N for _ in range(N)]
for _ in range(M):
    u, v = mii()
    arr[u].append(v)
    arr[v].append(u)

visited = [False] * N
chk = False

def dfs(node, depth):
    global chk
    visited[node] = True

    if depth == 4:
        chk = True
        return

    for nxt_node in arr[node]:
        if visited[nxt_node]:
            continue
        dfs(nxt_node, depth + 1)
    
    visited[node] = False

for i in range(N):
    dfs(i, 0)
    
    if chk:
        break

if chk:
    print(1)
else:
    print(0)