[python] programmers - 부대복귀

https://school.programmers.co.kr/learn/courses/30/lessons/132266?language=python3

프로그래머스

SOLUTION  📝

 

- sources들을 개별적으로 보는 것이 아닌 도착점에서 갈 수 있는 지점/거리 체크

- graph에 미리 특정 지점에서 갈 수 있는 위치들을 확인하여 roads를 반복하여 확인하지 않도록 함

- dictionary.get(x, y) 함수의 사용: 두 개의 인자 사용 가능 => x는 찾고자 하는 값, y는 return 값이 없을 때 반환할 값

- 차후 공부 대상 : 유사 딕셔너리(defaultdict) 사용해보기

 

CODE 📌

from collections import deque

def solution(n, roads, sources, destination):

	# 정답 변수
    answer = []
    
    # 변수 정의
    check = [0]*(n+1) # 방문 여부 확인
    now = deque([destination]) # 현재 갈 수 있는 위치 정보 저장
    possible = {destination: 0} # 목적지에 도착까지 걸리는 거리
    
    check[destination] = 1 # 시작점 방문 처리
    
    # i 지점에서 갈 수 있는 위치 정보 저장 ex) 1: [2, 3] => 1에서는 2, 3으로 이동할 수 있음
    graph = {i: [] for i in range(1, n+1)}
    
    # graph에 정보 저장
    for a, b in roads:
        graph[a].append(b)
        graph[b].append(a)
    
    # 갈 수 있는 위치가 남아있다면
    while now:
    	# s는 갈 수 있는 지점들 중 한 포인트
        s = now.popleft()
        # graph에 미리 저장했던 s에서 갈 수 있는 포인트들
        for e in graph[s]:
        	# 이미 갔던 곳은 다시 보지 않는다
            if check[e] == 0:
				# 방문 체크 및 갈 수 있는 위치 정보로 저장, 그리고 목적지 도착 거리 저장
                check[e] = 1
                now.append(e)
                possible[e] = possible[s]+1
    
    # get 사용
    for s in sources:
        answer.append(possible.get(s, -1))
                
    return answer