[파이썬] 부대복귀

💗 나의 풀이

from collections import defaultdict, deque

def solution(n, roads, sources, destination):
    answer = []
    dic = defaultdict(list)
    check = [-1] * (n + 1)

    for s, e in roads:
        dic[s].append(e)
        dic[e].append(s)

    def bfs(start):
        nonlocal check
        que = deque([(start, 0)])
        while que:
            cur, distance = que.popleft()
            for k in dic[cur]:
                if check[k] != -1 : continue
                check[k] = distance + 1
                que.append((k, distance + 1))

    check[destination] = 0
    bfs(destination)

    for source in sources:
        answer.append(check[source])

    return answer  # 최단 시간 배열

source에서 destination으로 BFS를 하나씩 탐색하면 시간초과가 날 수 밖에 없다.

destination에서 갈 수 있는 모든 곳을 방문해서 배열에 기록한다.

 

 

# 시간 초과
from collections import defaultdict, deque

def solution(n, roads, sources, destination):
    answer = []
    dic = defaultdict(list)
    check = [0] * (n + 1)
    
    for s, e in roads :
        dic[s].append(e)
        dic[e].append(s)
        
    def check_bfs(start) :
        nonlocal check
        que = deque([start])
        while que :
            cur = que.popleft()
            if check[cur] : continue
            check[cur] = 1
            for k in dic[cur] :
                if check[k] : continue
                que.append(k) 
    
    def bfs(start) :
        que = deque([(start, 0)])
        result = 0
        visited = [0] * (n + 1)
        while que :
            cur, distance = que.popleft()
            if cur == destination :
                return distance
            if visited[cur] : continue
            visited[cur] = 1
            for k in dic[cur] :
                if visited[k] : continue
                que.append((k, distance + 1))
    
    check_bfs(destination)
    for source in sources :
        if check[source] == 0 :
            answer.append(-1)
            continue
        answer.append(bfs(source))
        
    return answer   # 최단 시간 배열

아래 코드에서 보완한 점이 destination에서 방문한 위치들을 표시했다.

sources를 하나씩 탐색할 때 방문한 위치가 아니면 바로 -1을 answer에 추가

 

 

# 시간 초과
from collections import defaultdict, deque

def solution(n, roads, sources, destination):
    answer = []
    dic = defaultdict(list)
    
    for s, e in roads :
        dic[s].append(e)
        dic[e].append(s)
    
    def bfs(start) :
        que = deque([(start, 0)])
        result = 0
        visited = [0] * (n + 1)
        while que :
            cur, distance = que.popleft()
            if cur == destination :
                return distance
            if visited[cur] : continue
            visited[cur] = 1
            for k in dic[cur] :
                if visited[k] : continue
                que.append((k, distance + 1))
        return -1
    
    for source in sources :
        answer.append(bfs(source))
        
    return answer   # 최단 시간 배열

 

 

🌿 다른 사람 풀이

# https://velog.io/@hyg8702/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%B6%80%EB%8C%80%EB%B3%B5%EA%B7%80-python%ED%8C%8C%EC%9D%B4%EC%8D%AC#-%EB%AC%B8%EC%A0%9C-%ED%92%80%EC%9D%B4
from collections import deque

def solution(n, roads, sources, destination):
    
    visit = [-1] * (n + 1)
    graph = [[] for _ in range(n + 1)]
    for s, e in roads :
        graph[s].append(e)
        graph[e].append(s)
    
    Q = deque([destination])
    visit[destination] = 0
    while Q :
        now = Q.popleft()
        
        for node in graph[now] :
            if visit[node] == -1 :
                visit[node] = visit[now] + 1
                Q.append(node)
                
    return [visit[i] for i in sources]

destination에서 시작해서 BFS 탐색

나랑 같은 방법!

 

 

문제 출처 👇

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

프로그래머스