[알고리즘] 2644 촌수 계산
태그 = 레벨 / 'baekjoon' / 'algorithm' / 'Python3' / '백준'
게시물을 작성하면서 복습하는 문제를 선정하는 기준은<solved.ac 티어 실버 2 (Silver 2) 이상>입니다.
※ 본 사진과 해당 게시글 내용의 문제 모두 백준 : 온라인 저지[Baekjoon_OnlineJudge]사이트에서 발췌해왔습니다.
❓ 문제
백준 온라인 저지 (Baekjoon Online Judge) :2644 촌수 계산
❗ 풀이
My Code
메모리 : 32404KB
시간 : 88ms
메모리 : 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)
Author And Source
이 문제에 관하여([알고리즘] 2644 촌수 계산), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yummygyudon/알고리즘-2644-촌수-계산저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)