👩‍🎓공부 - 2024.01.09 오늘의 백준 문제풀이

13023번 - ABCDE

위와 같은 형식으로 친구관계가 이어져 있는 트리인지 확인해보면 되는 문제입니다.
이전 깊이 우선 탐색 문제를 풀듯 시간초과와 메모리 제한을 피하는게 쉽지 않았습니다.

N,M = map(int,input().split())
graph = [[] for _ in range(N)]
visited = [0]*N
depth = 0
for _ in range(M):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

일단 그래프, 방문여부(백트래킹), 측정 깊이 등을 받아주고 해당 인덱스.append(해당 값) 으로 친구관계를 그래프에 기록해주도록 합시다.

for i in range(N):
    result = dfs(i)
    if result == True:
        break
    depth = 0

그리고 여기서부터 시간초과를 피하기 위한 제 처절한 몸부림이 시작되는데...
dfs 리턴값이 True 가 나오면 친구관계를 만족한다고 지정하고 break를 쳐서 조금이라도 시간낭비를 줄이겠습니다. 그리고 탐색을 한번 돌면 다시 탐색을 돌도록 깊이를 초기화시켜줍니다.

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

시간초과 방지로 sysinput하고 recursionerror를 피하기위해 setrecursionlimit을 지정하겠습니다.

def dfs(N):
    global depth
    if depth > 3:
        return True

일단 저 depth > 3이라는 깊이가 만족할경우 함수탈출 이라는 코드를 위 아래 둘 다 적어줄 겁니다. PS사이트에서 확인해본 결과 제 코드에서 저걸 위에 하나 적거나 아래에 하나 적으면 시간초과로 통과하지 못하더라고요.

    visited[N] = 1
    for i in graph[N]:
        if not visited[i]:
            depth += 1
            dfs(i)

해당 인덱스 방문표시를 해주고 인덱스 안의 값을 방문하지 않았다면 깊이를 하나 더 올려주고 재귀를 통해 방문해주도록 합시다.

    visited[N] = 0
    if depth > 3:
        return True
    depth -= 1

만약 일차적으로 탐색이 끝났다면 (하위노드가 없고 자기자신이 리프노드) 해당 노드를 다른 방식으로 탐색할 수 있도록 방문여부를 초기화 해주겠습니다 (백트래킹 기법). 이전에 말씀드렸듯이 만약 depth가 4 이상이라면 True를 리턴합시다. 그리고 재귀가 끝나고 나온 코드이므로 이전 노드로 돌아가서 작업을 치기 위해 현재깊이 - 1로 이전 노드의 깊이를 설정해서 다시 탐색에 임해주도록 합시다.

if result == True:
    print(1)
else:
    print(0)

마지막으로 result가 True 값이 나오면 1, 아니라면 0을 출력하면 됩니다.

여담이지만 파이썬으로 DFS 활용문제를 해결할 때에는
항상 시간초과와 메모리 제한을 염두해두고 풀어야 할 것 같습니다.

전에 실버에서 트리문제같이 이차원 배열 빵빵하게 채워쓰게 되면 대부분 오류에 걸리는 거 같네요.