문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/86971
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
- 레벨 2
- 어떻게 풀어야할지 감도 안잡혀서 고민하다가 풀이를 찾아봤다
- https://jeongmin.tistory.com/5
[프로그래머스 Level 2] 전력망을 둘로 나누기 - 파이썬(Python)
✅문제 https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이
jeongmin.tistory.com
- 위 블로그를 참고했고 30분은 커녕 몇시간은 앉아있어야 생각이 날만한 (내 입장에서는) 기발한 풀이였다..
- 일단 각자 노드에 연결 되어있는 노드들을 이중 리스트에 담아주고 각자 노드들과 이어진 노드의 개수를 bfs로 찾은 다음, v1과 v2의 사이를 끊는다면 노드의 개수가 몇개가 차이가날지 계산하는 방식이다
- 연결을 끊었을 때 노드 개수 차이는 v1과 v2를 서로의 리스트에서 없애준 다음 bfs를 돌려 이어진 노드 개수를 찾은 다음 abs(bfs(v1) - bfs(v2))로 그 차이를 찾을 수 있다
from collections import deque
def solution(n, wires):
def bfs(x):
queue = deque([x]) # 리스트 형식으로 넣어줘야 밑에 for loop에서 돌릴 수 있음
visited = [0] * (n + 1) # 방문 여부 확인
visited[x] = 1
count = 1
while queue: # 큐가 빌때까지
curr = queue.popleft()
for i in graph[curr]: # curr 노드랑 이어진 노드들을 돌면서 확인
if not visited[i]: # 방문한적 없다면
visited[i] = 1 # 방문처리
queue.append(i) # 큐에 넣어주기
count += 1 # 카운트 올리기
return count # 카운트 반환
graph = [[] for _ in range(n+1)]
for v1, v2 in wires: # graph리스트의 index = 현재 노드, nested 리스트 안에 이어진 노드들 저장
graph[v1].append(v2)
graph[v2].append(v1)
res = n # minimum을 찾아야되기 때문에
for v1, v2 in wires: # 완전 탐색 부분
graph[v1].remove(v2) # 연결 끊기
graph[v2].remove(v1)
res = min(abs(bfs(v1) - bfs(v2)), res)
graph[v1].append(v2) # 다시 이어주기
graph[v2].append(v1)
return res