게시물을 작성하면서 복습하는 문제를 선정하는 기준은<solved.ac 티어 브론즈 1 (Bronze1) 이상>입니다.

※ 본 사진과 해당 게시글 내용의 문제 모두 백준 : 온라인 저지[Baekjoon_OnlineJudge]사이트에서 발췌해왔습니다.

❓ 문제

백준 온라인 저지 (Baekjoon Online Judge) : 18352 특정 거리의 도시 찾기

❗ 풀이

My Code

메모리 : 108796KB
시간 : 2348ms

시작 위치가 정해져있어
BFS를 통한 경로 계산 풀이 했습니다.

import sys
input = sys.stdin.readline

Cities, Routes, Target, Start = map(int, input().split())

graph = [[] for _ in range(Cities+1)]
visited = [0]*(Cities+1)
distance = [1e9]*(Cities+1)
for i in range(Routes) :
    s, a = map(int, input().split())
    graph[s].append(a)


from collections import deque
q = deque()
q.append([Start, 0])
visited[Start] = 1
while q :
    s, dis = q.popleft()
    distance[s] = min(distance[s], dis)
    if graph[s] :
        for a in graph[s] :
            if visited[a] == 0 :
                visited[a] = 1
                q.append([a, dis+1])

isin = False
for i in range(len(distance)) :
    if distance[i] == Target :
        isin = True
        print(i)
if not isin :
    print(-1)

• graph : 각 위치에서 갈 수 있는 노드 주소 (경로) 를 저장

• visited : 작업 중 방문 여부 (중복 방문 방지)

• distance : 최단 거리 저장 ( 초반 기본값 : min함수를 위해 INF 대용 1e9로 저장 )

큐에 시작 노드를 넣고
시작 노드에서 갈 수 있는 각 도착 노드에 대한 거리를
min함수를 통해 계속해서 최단 거리를 갱신해주는 방법이다.

isin이라는 임의의 상태 flag를 만들어서

특정 최단 거리를 가진 노드를 발견하면
이 isin을 True로 변환하고
해당 노드를 출력한다.

isin이 반복문을 거쳤는데도 False라는 것은
해당 특정 거리를 가진 노드가 없다는 것이기 때문에
-1을 print한다.