태그 = 레벨 / 'baekjoon' / 'algorithm' / 'Python3' / '백준'

게시물을 작성하면서 복습하는 문제를 선정하는 기준은<solved.ac 티어 실버 2 (Silver 2) 이상>입니다.

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

❓ 문제

백준 온라인 저지 (Baekjoon Online Judge) :2644 촌수 계산

❗ 풀이

My Code

메모리 : 32404KB
시간 : 88ms

해당 문제는 경로 정보가 주어지고
시작 노드와 도착 노드가 주어지는

전형적인 BFS 활용문제이다.

시작 노드값과 이동횟수를 나타낼 cnt로 while문을 수행하고

최초로 도착한 값이 나왔을 때 cnt를 출력하고 루프문을 종료한다.

그 이후, 찾지 못했을 경우를 위해
found라는 상태 flag 변수를 통한
-1 조건 출력코드를 작성했다.

import sys
input = sys.stdin.readline
N = int(input())

start, end = map(int, input().split())
M = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(M) :
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

from collections import deque
q = deque()
visited = [0 for _ in range(N+1)]
q.append([start, 0])
visited[start] = 1
found = False
while q :
    now, cnt = q.popleft()
    if now == end :
        print(cnt)
        found = True
        break
    for v in graph[now]:
        if visited[v] == 0 :
            q.append([v, cnt+1])
            visited[v]=1
if found == False :
    print(-1)