Programmers - 전력망을 둘로 나누기

문제 링크

그래프를 순회하여 방문 횟수를 구하는 문제

Node의 개수가 100개밖에 되지 않고 Edge를 추가,제거하기 편하기 때문에 2차원 배열로 그래프를 구현하였다.

문제의 제약조건에 모든 Node가 하나의 Tree로 연결되어 있다고 나와있기 때문에 Edge를 1개 제거하면

임의의 Node X가 포함된 그래프의 Node 개수 + X가 포함되지 않은 그래프의 Node 개수 = 전체 Node 수

임을 알 수 있다.

def solution(n, wires):
    answer = 987654321
    g = [[False for _ in range(n)] for __ in range(n)]
    wires = list(map(lambda x: [x[0]-1, x[1]-1], wires))

    def search():
        visit = [False for i in range(n)]
        q = [0]
        while len(q) != 0:
            now = q.pop()
            visit[now] = True
            for (next, canMove) in enumerate(g[now]):
                if visit[next] or (not canMove):
                    continue
                q.append(next)
        networkA = len(list(filter(lambda x: x, visit)))
        networkB = n-networkA
        return abs(networkA-networkB)

    for [x, y] in wires:
        g[x][y] = g[y][x] = True

    # search
    for [x, y] in wires:
        g[x][y] = g[y][x] = False
        answer = min(search(), answer)
        g[x][y] = g[y][x] = True

    return answer