프로그래머스 문제 풀이(feat. 창업대회 우수상)

오늘은 BFS관련해서 문제를 몇개 풀었어서 관련된 문제들에 대한 풀이를 적어보려고 한다.

=>광주 어부바 창업대회 나가서 상금 200 탄날!

배달

만약 문제에 각각의 노드에 걸친 엣지에 가중치가 있고 거리에 대한 최솟값을 구하라 라고 한다면
다익스트라 알고리즘사용하자!

1. 출발 노드를 설정
2. 각 노드의 최소 비용을 저장
3. 방문하지 않은 노드 중에 가장 비용 적은거 선택
4. 해당 노드를 거쳐 특정한 노드로 가는 경우를 고려하여 최소 비용 갱신
5. N번 반복

heapq

이진트리 기반의 최소 힙 자료구조!

항상 정렬된 상태로 추가되고 삭제 -> 가장 작은값은 언제나 인덱스 0

최소 힙 생성 heapq = []
list를 최소 힙처럼 다루는거임!
heappush(heap,4)
heappop(heap)

o(logn)의 시간 복잡도를 가집니다
heap[0]도 가능 - 리스트니까 => 이게 heappop() 함수를 호출해서 원소 삭제 마다 최소값이 올라가는거
그래서 두번째 작은 원소가 heap[1]이 바로 있지 않을 수도!

float(‘inf’)는 무슨숫자와 비교해도 크다고 판정!!

import heapq
def dijkstra(dis,adj):
	heap = []
    heapq.heappush(heap, [0,1]) # 무조건 1번부터 시작이고 시작도 포함이어서 가중치 0 시작점1을 적음
    while heap:
    	cost, node = heapq.heappop(heap) # 이러면 가장 작은 숫자부터 나옴!
        for c,n in adj[node]: #이러면 각각의 점에 대해 연결된 노드의 가중치와 연결된 노드가 나옴
        	if dis[n] > cost+c:
            	dis[n] = cost+c
                heapq.heappush(heap, [cost+c, n]) # 그 다음부분으로 계속 연결되게만듬

def solution(N,road,K):
	answer= 0
    INF = float('inf')
    dis = [INF] *(N+1)
    adj = [[] for _ in range(N+1)]
    for r in road:
    	adj[r[0]].append([r[2],r[0]]) # 시작점에 가중치, 연결된 노드를 순서대로 적었다
        adj[r[1]].append([r[2],r[0]]) # 양방향이어서 끝점에서도 시작점까지 연결해주기
        
    dijkstra(dis,adj)
    
    return len([x for x in dis if x <=K])

전력망을 둘로 나누기

bfs문제였고 서로 연결된 부분을 한번 끊어서 두 줄이 각각 길이가 가장 비슷하게 만드는거!

즉 min을 사용해야했고, bfs를 사용하면 된다!
이때 줄을 끊는다 => 이미 방문을 했으니 세지 않는다로 이해하면 편하다!

from collections import deque, defaultdict
def bfs(start, visited,g):
	q= deque([start])
    result = 1
    visited[start] = True
    while q:
    	now=q.popleft()
        for c in g[now]:
        	if visited[c] == False: # 즉 전 노드랑 연결되어있는데  방문 안했을때
            	result +=1 # 길이 추가
                q.append(c) # 그 다음 부분으로 추가
                visited[c] = True
    return result
def solution(n,wires):
	answer = 999
     g = defaultdict(list)
    for a,b in wires:
        g[a].append(b)
        g[b].append(a)
    
    for start,not_visit in wires:
        visited = [False]* (n+1)
        visited[not_visit] = True
        visited[start] = True
        result = bfs(start,visited,g)
        answer = min(answer, abs(result - (n-result)))
    return answer

오늘 피드백

내일 드디어 네이버 결과 나온다!! 솔직히 이력서 많이 부족해서 애매하지만
시험을 코테 문제 5문제중 4문제를 풀었고
AI도 2문제 정도 제외하고 다 풀어서 시험은 자신있다!! -> 제발 합격하면!!!