오늘의 문제 | 프로그래머스: 전력망을 둘로 나누기
이번 문제는 그래프인가 했으나 읽어보니 완전 탐색 문제이긴 하다. 트리 형식이라길래 자식 노드가 2개만 있을까 했는데, 그림을 보니 개수에 제한은 없는 듯하다. 그래도 순환 형태는 없는 형태이기에 아래 아이디어로 해결하면 될듯하다.
아이디어: 루트 노드에서 뻗어나가서 만들어지는 개수를 확인하자.
각 노드를 루트라 생각하고, 뻗어나갈 수 있는 개수를 파악해보려 한다. 약간은 DFS를 써서 최대 깊이를 알아볼 필요가 있어보이긴 한다.
from collections import deque
def bfs(start,graph,visit):
d=deque([start])
visit[start]=1
idx=0
while d:
node=d.popleft()
idx+=1
for i in graph[node]:
if visit[i]==0:
d.append(i)
visit[i]=1
return idx
def solution(n, wires):
answer = n-2
for i in range(len(wires)):
l=wires[:]
start=0
graph=[[] for i in range(n+1)]
visit=[0 for _ in range(n+1)]
l.pop(i)
for a,b in l:
graph[a].append(b)
graph[b].append(a)
for a,b in enumerate(graph):
if b!=[]:
start = a
break
left=bfs(start,graph,visit)
right=n-left
if abs(left-right) < answer:
answer=abs(left-right)
return answer
오늘은 결국 검색 찬스를 써서 해결했다… 어느 정도 생각했던 로직은 비슷한데 완전 탐색은 이걸 구현하는게 문제라는 생각이 든다. 문제 알고리즘이 완전 탐색이라고는 했지만 결국은 그래프 탐색이었다. 알고리즘 힌트가 오히려 방해가 되지 않았나 싶다.
오늘의 회고
약간은 자존심을 내려놓고 검색 찬스를 쓰게 됐다. 난이도가 그리 어렵지 않았다는 생각에 약간 아쉽긴 하다. 프로그래머스는 디버깅을 할 수 없다는게 약간 단점으로 보인다. vs code에서 뭔가 방법이 있지 않을까 하는 생각도 든다.
'일기장 > 항해99클럽 4기' 카테고리의 다른 글
99클럽 코테 스터디 26일차 TIL: 베스킨라빈스 게임 (0) | 2024.11.22 |
---|---|
99클럽 코테 스터디 25일차 TIL: 골드 완전 탐색 (0) | 2024.11.22 |
99클럽 코테 스터디 23일차 TIL: Python Itertools (1) | 2024.11.19 |
99클럽 코테 스터디 22일차 TIL: 기본 완전 탐색 (0) | 2024.11.18 |
99클럽 코테 스터디 21일차 TIL: 완전 탐색 기초 (0) | 2024.11.17 |