[백준-Python] 촌수계산 : 2644번

🥈Silver2

https://www.acmicpc.net/problem/2644

 

 

 

✅ 정답풀이

import sys
from collections import deque

input = sys.stdin.readline


def bfs(start,end):

    queue=deque([start])
    visited[start]=0 # 시작지점: 거리 0

    while queue:
        cur=queue.popleft()

        # 목표 지점 도달하면 거리 반환
        if cur==end:
            return visited[cur]
           

       # 인접 노드 방문

        for neighbor in graph[cur]:
            if visited[neighbor]==-1: # 방문하지 않은 노드
                queue.append(neighbor)
                visited[neighbor]=visited[cur]+1


    return -1

n = int(input())
start, end = map(int, input().rstrip().split())  # target


graph = [[] for _ in range(n + 1)]
visited = [-1] * (n + 1) # start 기준 거리

m = int(input())

for _ in range(m):
    p, c = map(int, input().rstrip().split())
    graph[p].append(c)
    graph[c].append(p)

result=bfs(start,end)
print(result)

#7 3
# 7 방문
# 2 방문
# 1 방문
# 8 방문
# 9 방문
# 3 방문
# 도착 3

 

메모리	실행시간
34044	60

 

촌수계산은 최단거리 찾기의 문제라고 보면 되기때문에 BFS를 이용해 문제를 풀어보았다.

최단거리 계산 문제를 풀어보는게 처음이였는데 그래프를 순회할때 중복여부를 해줘야하는데, 이 배열(visited)을 활용해 start 기점부터 이동한 거리를 저장하다가 target을 발견하면 현재 순회중인 vertex의 visited 값을 리턴해주었다.

 

❗️ BFS는 탐색하는 순서가 레벨별로 이루어지므로, 먼저 방문하는 노드가 최단 거리임을 보장할 수 있다.

 

bfs 함수에서 인접노드를 순회하면서 방문하지 않은 노드를 찾아 queue에 넣어주고, visited 중복여부를 위한 값으로 누적의 개념으로 visited[cur]에 인접노드이므로 1을 더해서 업데이트를 해준다.