Notice
Recent Posts
Recent Comments
Link
«   2025/05   »
일 월 화 수 목 금 토
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
Tags more
Archives
Today
Total
관리 메뉴

짱이 될거야

백준 2644: 촌수계산 Python (DFS, BFS) 본문

알고리즘

백준 2644: 촌수계산 Python (DFS, BFS)

짱이 되었어 2022. 10. 12. 11:39

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

 

2644번: 촌수계산

사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어

www.acmicpc.net

 

 

1. BFS

import sys
input = sys.stdin.readline


def bfs(v):
    q = [v]
    while q:
        v = q.pop()
        for w in adj[v]:
            if relation[w] == 0:
                relation[w] = relation[v] + 1
                q.append(w)


N = int(input())    # N: 전체 사람의 수
a, b = map(int, input().split())    # A, B: 촌수를 계산해야 하는 두 사람의 번호
M = int(input())    # M: 부모 자식들 간의 관계의 개수
adj = [[] for _ in range(N+1)]    # 부모 자식간의 관계
for _ in range(M):
    x, y = map(int, input().split())
    adj[x].append(y)
    adj[y].append(x)

relation = [0] * (N+1)  # 촌수 계산
bfs(a)
print(relation[b] if relation[b] else -1)

 

 

2. DFS

def dfs(v):
    for w in adj[v]:
        if relation[w] == 0:
            relation[w] = relation[v] + 1
            dfs(w)


N = int(input())    # N: 전체 사람의 수
a, b = map(int, input().split())    # A, B: 촌수를 계산해야 하는 두 사람의 번호
M = int(input())    # M: 부모 자식들 간의 관계의 개수
adj = [[] for _ in range(N+1)]    # 부모 자식간의 관계
for _ in range(M):
    x, y = map(int, input().split())
    adj[x].append(y)
    adj[y].append(x)

relation = [0] * (N+1)  # 촌수 계산
# bfs(a)
dfs(a)
print(relation[b] if relation[b] else -1)

'알고리즘' 카테고리의 다른 글

백준 2667: 단지번호붙이기 Python (DFS, BFS)  (0) 2022.10.13
백준 1926: 그림 Python (BFS)  (0) 2022.10.12
백준 14888: 연산자 끼워넣기 Python (순열, DFS)  (0) 2022.10.11
프로그래머스: 최솟값 만들기  (0) 2022.10.10
프로그래머스(스택/큐): 같은 숫자는 싫어  (0) 2022.10.03
'알고리즘' Related Articles more
Comments