[TIL_Carrotww] 55 - 22/11/18

📝Carrotww의 코딩 기록장

🧲 python algorithm

🔍 programmers 부대복귀 level3
어제 풀던 문제다.
못 풀었었는데 한 가지를 더 생각하지 못 했다.
sources 를 반복문으로 돌리기 보다 destination을 출발지로 잡으면 모든 출발지와의 거리가 나오는거거늘...
이 사실을 깨달았을때 진짜... 너무... 아쉬웠다.
밑에는 나의 풀이이다.

• 풀이

from collections import deque, defaultdict

def solution(n, roads, sources, destination):
    roads_path = defaultdict(list)
    for a, b in roads:
        roads_path[a].append(b)
        roads_path[b].append(a)

    queue = deque([destination])
    visited = {x:-1 for x in range(1, n+1)}
    visited[destination] = 0
    while queue:
        cur_road = queue.popleft()
        cur_dis = visited[cur_road]
        for nxt_road in roads_path[cur_road]:
            if visited[nxt_road] == -1:
                visited[nxt_road] = cur_dis + 1
                queue.append(nxt_road)
    return [visited[x] for x in sources]

어제와 같이 visited key 값에는 n의 개수만큼 초기화 해주고 value 는 -1로 초기화 해주었다.
방문한 길은 0으로 바꾸어 주었다.

return 값은 visited에서 sources에 담겨있는 숫자들만 뽑아서 result에 담아주었다.

살짝 꼰 문제이지만 잘 생각해보면 풀 수 있었던 문제였다.
나 처럼 한 생각의 틀 안에 갇히는 것 만 아니였다면..ㅠ

테스트 케이스 10~15 번 과 같이 구조적으로 bfs 의 출발지가 여러 곳 이였다면 풀 수 없는 문제였다.

오늘 끝!