사이트 #문제: 문제유형 / 난이도

문제 링크 : https://www.acmicpc.net/problem/2644

🔍 Inspection

문제 접근(문제 분석 → 풀이 아이디어)

• 유형 : (전형적인) BFS 문제

  촌수 = 본인 y 에서 대상 x 까지 도달하는데 걸리는 (최단)edge 개수

• 문제 요약

  • 부모 - 자식 사이를 1촌이라고 정의한다

    (할 -나 :2 / 아부지 자식 - 나 : 3촌)

  • N 명의 사람들의 부모자식 관계를 입력으로 주어질때 , 주어진 두 사람의 촌수를 출력하라 (무관하면 -1 출력)

🚩 FLOW

코드를 풀이할 때 적었던 플로우가 있나요?

1. 입력 변수 및 양방향 인접 리스트 nodes 정의 및 초기화
2. 대상 부모 tx ↔ 자식 ty 까지의 최단 거리를 구하기 : BFS 사용
   • 촌수 = BFS 의 level
   • 큐 q = [tx ,0] # 대상 부모 tx 와 tx 와의 level 값을 할당
   • BFS 탐색 중 만약 대상 ty와 같을 경우 , 현재 level cn 로 정답 업데이트 후 탐색 종료
   • 현재 cn 과 직접적인 관계 가짐& 미방문한 번호만 q , visited 에 추가

🚩제출한 코드

import sys
from collections import deque
input = sys.stdin.readline

#1. 입력 변수 

N = int(input())
nodes = [[] for _ in range(N+1)]
tx , ty = map(int, input().split())

# 인접 리스트 nodes 만들기(양방향)
M = int(input())
for _ in range(M):
    x,y= map(int,input().split())
    nodes[x].append(y)
    nodes[y].append(x)

# 2.x -> y 의 최단 거리 찾기 : BFS
# 거리 = BFS의 level
q = deque([[tx , 0] ]) # 현재 번호 & level 정보를 queue 담기
visited = []
answer = -1
while q : 
    cn , cl = q.popleft() 
    if cn == ty : # target 값에 도달할때만 촌수를 answer에 업데이트 하기
        answer = cl 
        break
    for nn in nodes[cn]: # cn과 연결된 번호 & 미방문 -> 방문
        if nn not in visited : 
            visited.append(nn)
            q.append([nn ,cl+1] )

print(answer)

다른 사람 풀이 : 촌수를 추가적인 배열 v 에 정의&할당함

https://www.youtube.com/watch?v=j1qZDHllov8&t=4s

def bfs(s, e):
    q = []
    v = [0]*(N+1)

    q.append(s)
    v[s] = 1

    while q:
        c = q.pop(0)
        if c == e:          # 목적지 찾음
            return v[e]-1   # 나와 한칸 떨어져있으면 1촌

        # c와 연결된 번호인 경우 미방문이면 방문!
        for n in adj[c]:
            if not v[n]:
                q.append(n)
                v[n] = v[c]+1

    # 이곳의 코드를 실행했다면... 찾지못함!
    return -1

N = int(input())
S, E = map(int, input().split())
M = int(input())
adj = [[] for _ in range(N+1)]
for _ in range(M):
    p, c = map(int, input().split())
    adj[p].append(c)
    adj[c].append(p)

ans = bfs(S, E)
print(ans)

🚩결과