[프로그래머스][LV.2] 전력망을 둘로 나누기 | python3

2025. 3. 16. 13:09ㆍ프로그래머스/LV.2

문제설명

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

제한조건

- n은 2 이상 100 이하인 자연수입니다.
- wires는 길이가 n-1인 정수형 2차원 배열입니다.
- wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
- 1 ≤ v1 < v2 ≤ n 입니다.
- 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.

문제풀이

와 어려웠다. 다른 풀이를 참고해가며 이해하는데도 오래걸렸다.

bfs로 푼 풀이를 참고했다.

BFS (Breadth-First Search, 너비 우선 탐색)

1. BFS란?

BFS는 그래프 탐색 알고리즘 중 하나로, 가까운 노드부터 탐색하는 방식이다. 즉, 특정 노드를 방문한 후, 그 노드와 직접 연결된 모든 노드를 먼저 방문한 다음, 점점 더 먼 노드를 탐색한다.

➡ 즉, BFS는 "넓게 탐색하는 방식"의 알고리즘이다.

2. BFS의 동작 원리

BFS는 큐(Queue) 자료구조를 이용하여 탐색을 진행한다.

BFS 탐색 과정

탐색을 시작할 노드를 큐에 넣고 방문 처리한다.
큐에서 노드를 하나 꺼내고, 그 노드와 연결된 방문하지 않은 노드들을 큐에 추가한다.
위 과정을 큐가 빌 때까지 반복하면 모든 연결된 노드를 탐색할 수 있다.

3. BFS 예제

예제 그래프

이 그래프는 다음과 같이 연결되어 있다:

1번 노드는 2번, 3번과 연결됨
2번 노드는 1번, 4번과 연결됨
3번 노드는 1번, 5번과 연결됨
4번 노드는 2번과 연결됨
5번 노드는 3번과 연결됨

BFS 탐색 과정 (시작 노드 = 1)

시작 노드 1을 큐에 넣고 방문 처리
큐: [1], 방문: {1}
큐에서 1을 꺼내고, 1과 연결된 2, 3을 큐에 추가
큐: [2, 3], 방문: {1, 2, 3}
큐에서 2를 꺼내고, 2와 연결된 4를 큐에 추가
큐: [3, 4], 방문: {1, 2, 3, 4}
큐에서 3을 꺼내고, 3과 연결된 5를 큐에 추가
큐: [4, 5], 방문: {1, 2, 3, 4, 5}
큐에서 4를 꺼내고, 새로운 노드가 없으므로 그대로 유지
큐: [5], 방문: {1, 2, 3, 4, 5}
큐에서 5를 꺼내고, 탐색 종료
큐: [], 방문: {1, 2, 3, 4, 5}

➡ 최종 탐색 순서: 1 → 2 → 3 → 4 → 5

4. BFS 코드 구현 (파이썬)

from collections import deque

def bfs(graph, start):
    visited = set()  # 방문한 노드를 저장할 집합
    queue = deque([start])  # 큐 초기화 (시작 노드 삽입)
    visited.add(start)  # 시작 노드 방문 처리

    while queue:  # 큐가 빌 때까지 반복
        v = queue.popleft()  # 큐에서 노드를 꺼냄
        print(v, end=" ")  # 방문한 노드 출력

        for neighbor in graph[v]:  # 현재 노드와 연결된 모든 노드 탐색
            if neighbor not in visited:  # 방문하지 않은 노드라면
                queue.append(neighbor)  # 큐에 추가
                visited.add(neighbor)  # 방문 처리

# 예제 그래프 (인접 리스트 표현)
graph = {
    1: [2, 3],
    2: [1, 4],
    3: [1, 5],
    4: [2],
    5: [3]
}

# BFS 실행 (1번 노드부터 시작)
bfs(graph, 1)

출력 결과

1 2 3 4 5

➡ 가까운 노드부터 차례대로 탐색하는 것을 확인할 수 있다.

5. BFS vs DFS 비교

BFS (너비 우선 탐색) DFS (깊이 우선 탐색)

탐색 방식	가까운 노드부터 탐색	한 방향으로 끝까지 탐색 후 백트래킹
자료구조	큐(Queue)	스택(Stack) 또는 재귀(Recursion)
탐색 순서	넓게 탐색	깊게 탐색
활용 예시	최단 거리 탐색, 네트워크 연결 찾기	백트래킹(예: 미로 찾기), 순열/조합 문제

6. BFS의 활용 예시

최단 경로 찾기
- 예: 미로에서 출구까지 가장 빠른 길 찾기
- BFS는 가장 먼저 도착한 경로가 최단 경로이므로, 최단 거리 문제에 적합함.
네트워크 연결 탐색
- 예: 전력망 연결된 송전탑 찾기
- 어떤 노드가 다른 노드와 연결되어 있는지를 찾을 때 유용함.
웹 크롤링
- 예: 웹사이트의 링크를 따라가며 정보를 수집할 때
- 가까운 페이지부터 차례로 방문하는 방식으로 BFS를 활용할 수 있음.
게임 AI
- 예: 체스나 보드게임에서 최적의 움직임 찾기
- BFS를 사용하여 적절한 수를 찾거나, 몬스터의 이동 경로를 계산할 수 있음.

7. 정리

✔ BFS는 가까운 노드부터 탐색하는 방식이며, 큐(Queue)를 사용한다.
✔ 최단 경로 찾기 같은 문제에서 효과적이다.
✔ 그래프를 탐색할 때 DFS와 비교하여 선택적으로 사용할 수 있다.

➡ BFS는 그래프에서 최단 경로 탐색 및 연결된 요소를 찾는 데 강력한 알고리즘이다!

wires에서 차례대로 전선을 빼고 뺀 전선을 제외한 나머지 전선을 탐색하여 graph 이중 리스트에 넣는다.

이 이중리스트에서 연결된 값이 있는 원소를 찾자마자 그 값을 리턴한다. (한 묶음 당 하나의 값만 알면 전체 탐색을 할 수 잇음)

연결된 노드에 방문 할때마다 count를 해주고 전부 방문하면 종료한다.

다른 묶음의 갯수는 전체 노드에서 count한 노드를 빼주면 구할 수 있다.

나의코드

from collections import deque

def bfs(graph, start,visited):
    queue = deque([start]) # 큐에는 start와 직,간접적으로 연결되어 있는 원소가 들어가게 됨.
    
    visited[start]=True # 현재노드(시작 노드) 방문 처리
    cnt =0
    
    while queue: # 큐가 빌때까지 반복
        v=queue.popleft()
        cnt+=1
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]: # v와 연결된 값 리스트
            if not visited[i]: # 방문하지 않은 원소 => False 이기 떼문에 앞에 not 처리
                queue.append(i)
                visited[i] = True
    return cnt # start와 직,간접적으로 연결된 노드의 수가 몇개인지
        
        

def solution(n, wires):
    answer = n-2 # 두 전력망이 갖게 되는 송전탑의 개수 차이의 절댓값 중 최댓값
    # 만약 n이 9라면 최대 차이는 1,8 일때로 8-1 = 7이 됨.
    
    for i in range(len(wires)):
        tmps=wires.copy()
        graph=[[] for i in range(n+1)] # 이중리스트
        print(graph)
        visited=[False] * (n+1)
        tmps.pop(i) # i번재 전선 제거 # 전선을 차례대로 제거
        for wire in tmps:
            x,y=wire
            graph[x].append(y) # x번재에 y값
            graph[y].append(x) # y번째에 x값 # 각 인덱스에 있는 리스트에 그 번호와 연결된 다른 값들이 들어있음
        for idx,g in enumerate(graph):
            if g != []: # n개의 송전탑 중 다른 송전탑과 연결된 송전탑을 시작점으로 지정
                start = idx # 연결된 노드가 있는 노드를 start 점으로 잡음
                break
                
        cnts=bfs(graph,start,visited) # bfs를 이용하여 시작점에서 다른 송전탑 탐색
        # 탐색 가능한 송전탑 갯수. => 즉 연결된 송전탑의 갯수
        other_cnts = n-cnts # 나머지 전력량 개수
        
        answer=min(answer,abs(other_cnts-cnts))
        
    return answer

참고하기

def solution(n, wires):
    ans = n
    for sub in (wires[i+1:] + wires[:i] for i in range(len(wires))):
        s = set(sub[0]) # 시작 노드 역할
        [s.update(v) for _ in sub for v in sub if set(v) & s] # s에 시작 노드와 연결된 노드 모두 들어감
        ans = min(ans, abs(2 * len(s) - n))
    return ans

집합자료형 사용, 이중 for문으로 모든 경우 탐색

for sub in (wires[i+1:] + wires[:i] for i in range(len(wires))):

이 코드가 전선을 끊는 역할을 함.

[s.update(v) for _ in sub for v in sub if set(v) & s]

sub 내의 모든 전선을 탐색 (for v in sub)
현재 s에 포함된 노드와 연결된 전선이라면 (if set(v) & s) # & :: 교집합 연산
- A & B는 집합 A와 B의 교집합(intersection)이 존재하는지 확인하는 연산
- set(v) & s의 결과가 비어 있지 않다면 (True) → v의 노드 중 하나 이상이 s에 포함되어 있음
- set(v) & s의 결과가 비어 있다면 (False) → v의 노드가 s에 포함되지 않음
s에 해당 전선의 모든 노드를 추가 (s.update(v))

'프로그래머스 > LV.2' 카테고리의 다른 글

[프로그래머스][LV.2] 큰 수 만들기 \| python3 (0)	2025.03.18
[프로그래머스][LV.2] 조이스틱 \| python3 (0)	2025.03.18
[프로그래머스][LV.2] 모음사전 \| python3 (0)	2025.03.15
[프로그래머스][LV.2] 소수 찾기 \| python3 (0)	2025.03.14
[프로그래머스][LV.2] 카펫 \| python3 (0)	2025.03.14

꾸준히

꾸준히

태그

최근글

댓글

공지사항

아카이브