Py) 프로그래머스 12978

https://programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달

 

1차 시도: 1시간

2차 시도: 20분

3차 시도: 15분

 

0. 입출력

 

1. 김예고리즘

1-1. 알고리즘

일부 노드 방문(임의의 경로), 규모가 크지 않음(road 길이 많아봤자 2000개) 임을 고려해서 bfs라고 생각했다.

bfs -> FIFO 를 사용하는 식이라고 알고 있어서 큐를 사용함

1) 맨 처음 방문 노드 방문 처리 후 그 다음 노드 큐에 append
2) 큐에 들어있는 순서대로 방문처리, 가중치 더하기, 그 다음 노드 추가를 진행
   --> 각각의 경우의 가중치는 어떻게 처리하지..?
*) answer에 append해서 max 값을 뽑아내는 것을 생각했으나..
방문 마을을 관리하는 visited 배열 초기화 안함, town 초기화 안함 (사실 알고 있었는데 고치려고 하니까 시간도 다 되고, bfs 제대로 모르는데 고민할 바엔 답 보고 공부하자 싶었음)

1-2. 코드 (틀림)

from collections import deque
def solution(N, road, K):
    answer = []
    total = 0   # 시간 확인
    town = 1    # 마을 수 확인
    que = deque()
    visited = [False] * len(road)

    idx = 1     # 1번 마을을 찾을 예정
    tmax = 1
    for r in range(len(road)):
        if road[r][0] > tmax:
            tmax = road[r][0]
        if road[r][0] == 1:
            que.append(road[r][1])     # 1번 도로면 그 다음 탐색할 애를 넣는다
            visited[road[r][0]-1] = True


    while town <= N:
        top = que.popleft()-1
        visited[top] = True         # 방문 처리
        total += road[top][2]
        town += 1

        next = road[top][1]-1
        if visited[next] == False:
            que.append(next)    # 그 다음 탐색

        answer.append(town)


    return max(answer)

 

2. Solution

2-1. 사용 자료구조 및 알고리즘: 큐(FIFO), BFS

2-2. 로직

1) 양방향 그래프이므로 양방향 그래프를 dictionary로 만들어줌, key값이 마을 번호고 그 마을에 연결된 노드들은 전부 value로 넣어줌
2) distance라는 dictionary를 만들어주는데, 1번 마을의 경우를 제외하고 길이를 모두 infinity로 만들어줌.
1번 마을은 0 -> 1번 마을에서 1번 마을 가는건 가중치가 없다!
3) 큐에 1번 마을을 먼저 넣어주고, 큐에서 뽑아내 현재 노드 위치 파악.
해당 노드의 다음 노드와 길이를 찾아낸 뒤, 다음 노드까지의 거리가 현재노드 + 다음노드까지 거리 보다 작을 경우 갱신해준다.     -> 이런 방식으로 길이가 짧은 경우만 저장함.
4) 다음 노드를 넣어주고 1번 마을의 value 수 만큼 반복함

2-3. 코드

from collections import deque

def solution(N, road, K):
    answer = 0

    nodes = {}
    for v1, v2, dis in road:
        nodes[v1] = nodes.get(v1, []) + [(v2, dis)]
        nodes[v2] = nodes.get(v2, []) + [(v1, dis)]

    distance = {i:float('inf') if i != 1 else 0 for i in range(1, N + 1)}

    # 1번 노드와의 거리 저장
    deq = deque([1])
    while deq:
        current_node = deq.popleft()
        for next_node, dis in nodes[current_node]:
            if distance[next_node] > distance[current_node] + dis:
                distance[next_node] = distance[current_node] + dis
                deq.append(next_node)

    answer = len([True for val in distance.values() if val <= K])

    return answer

 

2-4. 새롭게 알게 된 것들!

# 1

distance = {i:float('inf') if i != 1 else 0 for i in range(1, N + 1)}

뒤에서 부터 해독한다. 1<=  <N+1의 범위에서, 1이라면 0으로, 1이 아니라면 float('inf')로 초기화

#2 float('inf')는 무한을 의미함

#3 

answer = len([True for val in distance.values() if val <= K])

distance 딕셔너리의 value들을 val 변수로 하나씩 파악하는데, K보다 작은 것들을 True라고 취급하고, True의 개수를 세어준다.

 

3. 피드백

#1

for v1, v2, dis in road:
    node[v1] = node.get(v1, []) + ([v2, dis])
    node[v2] = node.get(v2, []) + ([v1, dis])
    # 이렇게 넣으면 다음 노드, 가중치가 분리되는게 아니라 한 array에 들어간다

다시 풀면서 [(v2, dist)]를 괄호를 반대로 씀, 튜플 형태로 분리되어서 들어가는게 아니라 하나의 array에 원소로 다 들어가버림.

 

#2. 항상 헷갈리는거

deq = deque([1])    # [1]을 deque의 형태로 넣어줌

이라는 뜻임

#3

distance = {i:float('inf') if i != 1 else 0 for i in range(1, N+1)}

한줄로 써놓은 코드 감싸고있는게 { } 즉, 딕셔너리 형태라는 소리

#4 distance.values()에서 values 계속 까먹음. value로 계산해야하니까 챙겨줘야함