[programmers] 부대복귀 (python)

https://school.programmers.co.kr/learn/courses/30/lessons/132266

프로그래머스

---

처음에는 BFS로 매 source마다 desination까지의 거리를 측정하였다.

위의 방식을 사용하면 테스트 케이스 11~15에서 시간초과가 발생하였다.

어떻게 해결할지 몰라서 방법을 찾아봤는데 destination을 기준으로 서치를 진행하여 각 위치까지의 거리를 측정하면 되는 문제였다.

이마를 탁 치게 된 풀이였다.. 거꾸로 생각해보기

---

# 시간 초과 실패 코드
from collections import deque
def solution(n, roads, sources, destination):
    answer = []
    
    # 도로 저장
    graph = {i: [] for i in range(1, n + 1)}
    for road in roads:
        graph[road[0]].append(road[1])
        graph[road[1]].append(road[0])
        
    def bfs(pos):
    	# 시작 지점이 도착지인 경우 0 
        if pos == destination:
            answer.append(0)
            return
        
        visited = [False] * (n + 1)
        q = deque()
        visited[pos] = True
        q.append((pos, 0))
        
        while q:
            now, time = q.popleft()
            
            for i in graph[now]:
                if i == destination:
                    answer.append(time + 1)
                    return
                if not visited[i]:
                    q.append((i, time + 1))
                    visited[i] = True
        answer.append(-1)
        
    for source in sources:
        bfs(source)
    return answer

 

# 도착 지점 기준으로 각 위치까지의 거리를 구하여 해결한 방법
from collections import deque
def solution(n, roads, sources, destination):
    answer = []
    
    # 도로 저장
    graph = {i: [] for i in range(1, n + 1)}
    for road in roads:
        graph[road[0]].append(road[1])
        graph[road[1]].append(road[0])
    
    # 각 지역마다 걸리는 시간 저장
    times = [1e6] * (n + 1)
    times[destination] = 0
    
    def bfs(pos):
        visited = [False] * (n + 1)
        q = deque()
        visited[pos] = True
        q.append((pos, 0))
        
        while q:
            now, time = q.popleft()
            for i in graph[now]:
                if not visited[i]:
                	# 기존의 시간보다 적게 걸리는 경우에만 갱신
                    if times[i] >= time + 1:
                        times[i] = time + 1
                        q.append((i, time + 1))
                        visited[i] = True
    
    # 도착 지점을 기준으로 bfs 진행
    # 각 지역마다 도착지로부터의 거리를 저장
    bfs(destination)
    
    for source in sources:
        if times[source] == 1e6:
            answer.append(-1)
        else:
            answer.append(times[source])
    return answer