5286. [파이썬 SW 문제해결 최적화] 5일차 - 그래프 색칠하기 (트리 탐색 정리)

트리 탐색을 하는 김에 재귀 깊이 우선 탐색, 스택을 이용한 깊이 우선 탐색과 너비 우선 탐색 코드를 다 해보고 정리해봤다.

import sys
from collections import deque

sys.stdin = open("sample_input.txt", "r")

def color_tree(n):
    global result

    Q = deque()
    Q.append((1,[0] * (N + 1)))
    while Q:
        n, c = Q.pop()
        if n == N+1:
            # print("possible")
            result = 1
            return

        cn = [0] * (N+1)
        for t in range(1, N+1):
            if WM[n][t] == 0: continue
            else: cn[t] = c[t]
        for m in range(1,M+1):
            if m in cn: continue
            c[n] = m
            # print(n, m, c[:])
            Q.append((n+1,c[:]))

    # if n == N+1:
    #     print("possible")
    #     result = 1
    #     return
    #
    # cn = [0] * (N+1)
    # for t in range(1, N+1):
    #     if WM[n][t] == 0: continue
    #     else: cn[t] = C[t]
    #
    # for m in range(1,M+1):
    #     if m in cn: continue
    #     C[n] = m
    #     print(n, m, C)
    #     color_tree(n+1)
    #     C[n] = 0
    # return

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    N, E, M = map(int, input().split())
    WM = [[0]*(N+1) for _ in range(N+1)]
    for _ in range(E):
        f, s = map(int, input().split())
        WM[f][s], WM[s][f] = 1, 1

    C = [0] * (N + 1)
    result = 0
    color_tree(1)

    print("#{}".format(test_case),result)
    # ///////////////////////////////////////////////////////////////////////////////////

재귀를 이용한 깊이 우선 탐색의 경우 잘 작동했다. 단지 이 문제의 경우에는 가능한 경우의 수를 한가지만 찾으면 되기 때문에 이미 가능한 걸 알았는데도 더 찾는건 낭비인 것 같았다. 그래서 큐에 쌓는 방식을 생각하기로 했다. 또 개인적으로 재귀를 싫어하기도 한다.

Q를 만들고 쌓게 한 뒤 뒤에서부터 pop하면 깊이 우선 탐색이 되지만 사실 재귀랑 방식이 다르게 작동한다. 한번 따져 보자.

만약 이진 트리라면 깊이 h의 경우 h+1인 왼쪽 자식과 오른쪽 자식으로 들어간다. 재귀의 경우 왼쪽이 가능한 경우 바로 호다닥 자식으로 들어가 진행하는 반면 Q 스택 방식은 일단 왼쪽 자식, 오른쪽 자식을 둘 다 스택에 넣고 왼쪽자식으로 들어간다. 이런식으로 조금 다른 것 같다.

재귀는 함수가 쌓여있어서 return을 해도 계속 쌓여있던 함수가 실행되는 반면 이 스택방식은 while문을 이용하기 때문에 return 하자마자 묻지도 따지지도 않고 바로 함수를 끝내는 모습이다.

만약 경우의 수를 더 찾더라도 계속 찾고 싶으면 return 대신 continue 등을 통해 Q가 빌 때 까지 반복하면 그만이다.

Q를 popleft로 바꾸면 너비 우선 탐색이 된다.

또 스택을 이용할 때 주로 tuple을 이용해서 정보를 넘긴다. 근데 튜플 안에서 리스트를 넘겨서 저장하면 후에 그 리스트가 변경될 시 안의 내용도 같이 변경된다는 것을 알았다. 만약

A = [1,2,3]

Q.append((A))

로 저장하면 처음 Q 안에는

Q : [([1,2,3])]

로 되어있지만 만약

A[2] = 5

Q.append((A))

를 실행하면

Q: [([1,2,3]),([1,2,5])]

가 아니라

Q: [([1,2,5]),([1,2,5])]

로 되어 기존에 저장되었던 A의 리스트도 바뀐다. 이는 리스트 값을 저장할 때 파이썬도 주소값으로 저장해서 그런 것 같다. 그래서 위 코드를 잘 보면 append 할 시 그냥

Q.append((n+1,c))

가 아니라

Q.append((n+1,c[:]))

로 리스트 뒤에 [:]를 붙여 통채로 복사해서 넣으라는 표시를 추가했다.