[위클리 챌린지] 9주차

https://programmers.co.kr/learn/courses/30/lessons/86971?language=python3

코딩테스트 연습 - 9주차

 

그래프 탐색 문제..?

 

아무튼 뭐 트리 그래프의 간선을 하나 지워서 두개의 트리를 만들때, 정점이 개수의 차의 최소값을 구하면된다.

 

 

 

- 풀이

1. 일단 어떤 간선을 지우는 것이 답인지 모르니까, 하나의 간선을 지운 graph를 만든다.

2. search함수에 graph와, 시작점(삭제한 간선의 정점 중 하나)를 인자로 넘겨준다.

3. stack을 시작점으로 초기화, 스택이 비어있을때(=더이상 탐색할 곳이 없을 때)까지 반복

4. 스택의 맨앞의 원소를 뽑아 탐색시작

EX ) n = 9    ,    wires = [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]
에서 graph = [[1, 3], [2, 3], [3, 4], [4, 5], [4, 6], [7, 8], [7, 9]] 이고, wires[i] = [4, 7]이면

g	stack	now(=stack[0])
[[1, 3], [2, 3], [3, 4], [4, 5], [4, 6], [7, 8], [7, 9]]	[4]	4
[[1, 3], [2, 3], [7, 8], [7, 9]]	[5, 6]	3
[[7, 8], [7, 9]]	[5, 6, 1, 2]	5
[[7, 8], [7, 9]]	[6, 1, 2]	6
[[7, 8], [7, 9]]	[1, 2]	1
[[7, 8], [7, 9]]	[2]	2

5. 두 트리의 정점의 개수의 차만 알면 되므로, 길이의 차에 대해 절대값을 취하고, answer추가

6. answer중 최소값 반환

 

 

 

- 코드

def solution(n, wires):
    answer = []
    graph = []
    for i in range(len(wires)):
        graph = [w for w in wires if not w==wires[i]]
        answer.append(abs(search(graph[:], wires[i][0]) - search(graph[:], wires[i][1])))
    return min(answer)

def search(g, s):
    stack = [s]
    while stack:
        now = stack.pop(0)
        for i in g[:]:
            if i[0] == now:
                stack.append(i[1])
                g.remove([i[0], i[1]])
            elif i[1] == now:
                stack.append(i[0])
                g.remove([i[0], i[1]])
    return len(g)