[BOJ] 2644

문제

import sys
from collections import defaultdict

input = sys.stdin.readline
n = int(input())
start,end = map(int,input().split())
m = int(input())
family = defaultdict(list)
parent = 0
for _ in range(m):
    s,e = map(int,input().split())
    if e == start : parent=s
    family[s].append(e)
if parent == end :
    print(1)
    exit(1)
cnt=1
stack=[[cnt,parent]]
def findParent(child):
    for parent,children in family.items():
        if child in children:
            return parent
    return -1
found=False
while stack:
    cnt,parent = stack.pop()
    if parent not in family: continue # 족보가 없다면
    if end not in family[parent]:
        grand = findParent(parent)
        if grand != -1:
            for sib in family[grand]:
                if sib == parent : continue
                stack.append([cnt+2,sib])
            stack.append([cnt+1,grand])
    else: # 형제 중에 있음
        found=True
        cnt+=1
        break
print(cnt if found else -1)

• 너무 어렵게 생각한 것 같다.

solutions

참고

찾아보니 이 문제는 시작지점부터 목표지점까지 몇번 거쳐야하는지 생각하는 단순 탐색 문제였다.
bfs로 입력받은 값 기준으로 시작해서 연결되어있는 곳을 찾아 +1씩 더해나가면 문제를 풀 수 있다.

from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
a, b = map(int, input().split())
m = int(input())
adj = [[] for i in range(n + 1)]
result = [0 for i in range(n + 1)]
def bfs(start):
    q = deque()
    q.append(start)
    visit = [0 for i in range(n + 1)]
    visit[start] = 1
    while q:
        d = q.popleft()
        for i in adj[d]: # 부모형제 리스트
            if visit[i] == 0:
                visit[i] = 1
                result[i] = result[d] + 1 # 그와 나의 관계는 여태 내가 지나온 관계 +1
                q.append(i)
for i in range(m):
    x, y = map(int, input().split())
    adj[x].append(y) # 부모와 자식 관계는 무조건 1, 같은 그룹으로 묶어놔도 상관 없다..
    adj[y].append(x)
bfs(a)
print(result[b] if result[b] != 0 else -1) # 그와 관계가 없다면 0 일것이니깐..

참고

# dfs
import sys
sys.setrecursionlimit(300000)

def dfs(node):
    for n in graph[node]:
        if check[n] == 0:
            check[n] = check[node]+1
            dfs(n)
            
n = int(input())
graph = [[] for _ in range(n+1)]
s, e = map(int, input().split())
for _ in range(int(input())):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
check = [0]*(n+1)
dfs(s)
print(check[e] if check[e] > 0 else -1)