[프로그래머스] Lv2 - 전력망을 둘로 나누기

프로그래머스 코딩테스트 고득점 Kit - 완전탐색

• Lv 2. 전력망을 둘로 나누기 (Python)
  https://school.programmers.co.kr/learn/courses/30/lessons/86971

Code

from collections import deque

def bfs(start_point, graph, visited, connected):
    q = deque()
    q.append(start_point)
    visited[start_point] = 1
    cnt = 1

    while (q):
        curr = q.popleft()

        for i in range(len(graph[curr])):
            next_point = graph[curr][i]
            if(visited[next_point] == 0 and connected[curr][next_point] == 0):      # 이전에 탐색하지 않았고 현재 노드와 연결되어 있다면 -> 카운트
                visited[next_point] = 1
                q.append(next_point)
                cnt += 1
    return cnt

def solution(n, wires):
    answer = n

    graph = [[] for _ in range(n + 1)]
    for wire in wires:
        graph[wire[0]].append(wire[1])
        graph[wire[1]].append(wire[0])

    # print(graph)

    # 끊고 -> 탐색 -> 카운트
    connected = [list(0 for _ in range(n + 1)) for _ in range(n + 1)]  # 0 이면 연결되어있고 1이면 끊겨있기

    for i in range(len(wires)):
        visited = [0 for _ in range(n + 1)]
        left = wires[i][0]
        right = wires[i][1]

        connected[left][right] = 1  # 현재 wires[i] 인 부분을 끊어보기
        connected[right][left] = 1

        left_count = bfs(left, graph, visited, connected)  # left에 붙어있는 전력망 개수
        right_count = bfs(right, graph, visited, connected)  # right에 붙어있는 전력망 개수

        connected[left][right] = 0  # 다음 탐색을 위해 다시 붙여두기
        connected[right][left] = 0

        answer = min(answer, abs(left_count - right_count))

    return answer

풀이 및 해설

• 첨에 defaultdict(list)로 하려다가 탐색하는거 넘 번거로워서 때려치고 갈아엎었따
• wires를 돌면서 한번씩 끊어보고 → 연결된거 각자 카운트하고 (여기서 BFS로 탐색) → 최솟값 찾기 하면 될거같았는데 생각보다 저 끊긴걸 어떻게 표현할지 고민이었다 흠 🧐
• 일단 **BFS** 쓰기로 마음 먹어서 생각해보니까 역시나 2차원 배열로 걍 냅다 표현하는게 직관적일거 같아서 결정
• 처음에 방향 잡는거에서 많이 해맨듯 생각보다 오래걸림 ㅠ.ㅠ
  차분하면 빨리 풀수있는 문제..같다.. !

DFS 풀이법

def dfs(v, graph, visited):
    visited[v] = True
    return sum([1] + [dfs(u, graph, visited) for u in graph[v] if not visited[u]])

def solution(n, wires):
    graph = [[] for _ in range(n+1)]
    for v, u in wires:
        graph[v].append(u)
        graph[u].append(v)

    answer = 100
    for i in range(n-1):
        visited = [False for _ in range(n+1)]
        v1, v2 = wires[i]
        visited[v2] = True
        tmp = abs(dfs(v1, graph, visited) - dfs(v2, graph, visited))
        answer = min(tmp, answer)

    return answer