18352. 특정 거리의 도시 찾기 - 파이썬. BFS, 큐

1. 사용한 알고리즘 | 자료 구조

• BFS
• 큐

2. 풀이 접근 방식

• 전형적인 BFS 문제입니다. 
• K회 만큼 BFS 연산 후 Queue 에 있는 값을 정렬, 출력합니다.

3. 특이사항

• Stack 2개를 스왑하는 방식으로 사용하여 deque 를 import 하지 않고 BFS 알고리즘을 구현할 수 있습니다. 

4. 언어 | 실행시간 | 메모리 사용량

• Python3 |  1264ms | 97164kb

from sys import stdin

def solution():
	# 1. 입력
    # N: 정점의 수 | M: 간선의 수 
    # K: BFS 연산 횟수 | X: BFS 연산 시작점
    N, M, K, X = map(int, stdin.readline().split())

	# 2. 선언
    # 2-1. paths: 간선 정보
	paths = [[] for _ in range(N + 1)]
    
	# 2-2. visited: 방문 여부 배열. 
    # 시작점 X는 '방문 완료' 처리. 
    visited = [False] * (N + 1)
    visited[X] = True

	# 2-3 BFS 연산을 위한 스택 2개 선언.
    current_path_stack = [X]
    next_path_stack = []


	# 1-1. 간선 정보 입력
    for _ in range(M):
        departure, destination = map(int, stdin.readline().split())
		# 단방향 경로 입력. 
		paths[departure].append(destination)

	# 3. 연산
    # K 회 BFS 연산
    for _ in range(K):
    	# 3-1 각 도시마다
        for current_city in current_path_stack:
            # 방문하지 않은 다음 도시를
            # Next_que 에 추가. 
            for next_city in paths[current_city]:
                if not visited[next_city]:
                    visited[next_city] = True
                    next_path_stack.append(next_city)
        # 스택 swap. 
        current_path_stack, next_path_stack = next_path_stack, []

	# 4. 출력
    if not current_path_stack:
        print(-1)
    else:
        for path in sorted(current_path_stack):
            print(path)

solution()