하루일문

[백준] 2644번 촌수계산 (파이썬) 본문

algorithm/baekjoon

[백준] 2644번 촌수계산 (파이썬)

support_u 2023. 2. 18. 00:19

문제

 

2644번: 촌수계산

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

www.acmicpc.net

풀이

DSF

def dsf(graph, n, visited):
    global cnt

    for j in graph[n]:
        if visited[j] == 0:
            visited[j] = visited[n] + 1
            dsf(graph, j, visited)


import sys
input = sys.stdin.readline

people = int(input())

graph = [[] for _ in range(people + 1)]
visited = [0] * (people + 1)

who_1, who_2 = map(int, input().split())

m = int(input())

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

cnt = 0
visited[who_1] = 1
dsf(graph, who_1, visited)


if visited[who_2] > 0:
    print(visited[who_2] - 1)
else:
    print(-1)

BFS

from collections import deque
def bsf(graph, n, visited):
    q = deque([n])
    visited[n] = 1

    while q:
        p = q.popleft()
        for j in graph[p]:
            if visited[j] == 0:
                visited[j] = visited[p] + 1
                q.append(j)

import sys
input = sys.stdin.readline

people = int(input())

graph = [[] for _ in range(people + 1)]
visited = [0] * (people + 1)
who_1, who_2 = map(int, input().split())
m = int(input())

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
bsf(graph, who_1, visited)

if visited[who_2] > 0:
    print(visited[who_2] - 1)
else:
    print(-1)

해설

두 방식으로 풀어봤다.
visited 리스트에 움직일 마다 +1을 해주는 방식으로 촌수를 구했다.
여기서 답을 내기위해 -1을 해주는 것은 필수이다.


아래 문제와 비슷한 방식으로 풀 수 있지만, 2644가 훨씬 쉬운 편이다.

 

[SW] 1949번 등산로 조성 (파이썬)

포인트 1. 상하좌우 이동 2. 이동 값 초기화 3. 땅을 판 뒤 판 땅도 초기화 4. 함수 나온 뒤도 초기화 5. k를 무조건 다 쓸 필요 없이 지금 땅 보다만 작으면 됨 풀이 # 상하좌우로 이동 dx = [1, -1, 0, 0]

support-u-oneday.tistory.com

 

'algorithm > baekjoon' 카테고리의 다른 글

[백준] 1926번 그림 (파이썬)  (1) 2023.02.18
[백준] 11651번 좌표 정렬하기 2 (파이썬)  (1) 2023.02.18
[백준] 11650번 좌표 정렬하기(파이썬)  (0) 2023.02.16
[백준] 11724번 연결 요소의 개수 (파이썬)  (0) 2023.02.16
[백준] 1764번 듣보잡 (파이썬)  (1) 2023.02.15
'algorithm/baekjoon' Related Articles more