문제

문제 링크

코드

from collections import deque
import traceback

alist: list
visited: list

def bfs(start):
    # print(f"start {start}")
    global alist, visited
    if visited[start] == 1:
        return -1
    cnt = 0
    q = deque()
    q.append(start)
    
    while q:
        now = q.popleft()
        # print(now)
        visited[now] = 1
        # print(visited)
        cnt += 1
        for node in alist[now]:
            if visited[node] == 0:
                q.append(node)
    # print("end")
    return cnt
        

def solution(n, wires):
    try:
        global alist, visited
        answer = []
        for except_wire in range(len(wires)):
            # print(f"except {except_wire+1}th wire")
            alist = [[] for _ in range(n+1)]
            visited = [0 for _ in range(n+1)]
            values = []
            for i, wire in enumerate(wires):
                if i == except_wire:
                    continue
                start, end = wire
                alist[start].append(end)
                alist[end].append(start)
            for i in range(1,n+1):
                result = bfs(i)
                if result != -1:
                    values.append(result)
            # print(f"values : {values}")
            answer.append(abs(values[0]-values[1]))
        # print(f"answer : {answer}")
        return min(answer)
    except:
        traceback.print_exc()
    

분석

전형적인 카카오 구현 문제 유형이다. (문제 분석이 중요한 유형)

문제 조건

1. 그래프의 노드 개수를 세는 함수를 구현한다.
   1. BFS 또는 DFS를 통해 완전 탐색 로직을 구현한다.
   2. 인접 리스트, 방문한 노드를 기록하는 리스트를 구현한다.
   3. 큐 또는 스택을 통해서 완전 탐색한다.
2. 주어진 와이어 중에서 하나의 와이어를 빼는 로직을 구현한다.
3. 1번과 2번 로직을 합쳐서 반복문을 통해 모든 와이어가 한번씩 빠진 상태로 노드의 개수를 세는 로직을 구현한다.
4. 모든 경우에서 문제에서 주어진 노드들 간의 개수 차이를 저장한다.
5. 개수 차이가 가장 적은 것을 반환한다.

감상

문제 조건은 간단했다. 이제 이렇게 쉬운 문제는 카카오에서 안 내지 않을까..