728x90
문제
https://www.acmicpc.net/problem/2644
첫번째 줄: 전체 사람의 수
둘째 줄: 촌수를 계산해야 하는 서로 다른 두 사람의 번호
셋째 줄: 부모 자식들 간의 관계의 개수
넷째 줄 부터 부모 자식간의 관계를 나타내는 두 번호 입력
여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성
------------------------------------------------------------------------------------------------------------------
풀이
def dfs(st, find):
ST = []
visited = [0] * (N+1)
ST.append(st)
visited[st] = 1
while ST:
v = ST.pop()
for w in G[v]:
if w == find: return visited[v]
if visited[w] == 0:
ST.append(w)
visited[w] = visited[v] + 1
return -1
import sys
N = int(sys.stdin.readline()) # 노드 개수
A, B = map(int, sys.stdin.readline().split())
R = int(sys.stdin.readline()) # 엣지의 개수
G = [[] for _ in range(N+1)]
for _ in range(R):
v1, v2 = map(int, sys.stdin.readline().split())
G[v1].append(v2)
G[v2].append(v1)
print(dfs(A, B))
728x90
'문제 풀이' 카테고리의 다른 글
[백준] 9012번: 괄호 - Python(파이썬) (0) | 2024.02.25 |
---|---|
[백준] 10773번: 제로 - Python(파이썬) (0) | 2024.02.25 |
[백준] 9610번: 사분면 - Python(파이썬) (0) | 2024.02.18 |
[백준] 2606번: 바이러스 - Python(파이썬) (0) | 2024.02.17 |
[백준] 2178번: 미로 탐색 - Python(파이썬) (0) | 2024.02.17 |