[Python]백준 2644/촌수계산/dfs/bfs

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

2644번: 촌수계산

⚡️ 문제 설명

여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

⚡️ 해결 방법

visited 배열은 촌수를 계산할 때 사용할 것이다.

입력받은 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때는 -1을 출력해야 한다. 그러므로 초기 배열을 -1로 해준다.

그리고 처음시작하는 자기자신을 0으로 바꿔준다.

info = [[] for _ in range(n + 1)]
for _ in range(m):
    x, y = map(int, input().split())
    info[x].append(y)
    info[y].append(x)
visited=[-1]*(n+1)
visited[a]=0

 

def dfs(x, y):
    for i in info[x]:
        if (visited[i]==-1):
            visited[i] = visited[x]+1
            dfs(i,y)
            
dfs(a,b)

 

 

처음 7을 방문 하였을 때 부모자식관계인 2를 0+1=1 해준다.

그다음 2와 부모자식 관계인 1,7,8,9를 1+1=2로 해준다.

1과 부모자식관계인 3을 2+1=3 해준다.

visited[3]이 답이 된다.

 

def bfs(x, y):
    queue = deque()
    queue.append(x)
    visited[x] = 0
    while queue:
        x= queue.popleft()
        if x == y:
            return
        for i in info[x]:
            if (visited[i]==-1):
                queue.append(i)
                visited[i] = visited[x]+1
bfs(a,b)

bfs는 큐를 활용하여 푼다.

 

⚡️ 코드

dfs

import sys
input = sys.stdin.readline

n = int(input())
a, b = map(int, input().split())
m = int(input())
info = [[] for _ in range(n + 1)]
for _ in range(m):
    x, y = map(int, input().split())
    info[x].append(y)
    info[y].append(x)

visited=[-1]*(n+1)
visited[a]=0
def dfs(x, y):
    for i in info[x]:
        if (visited[i]==-1):
            visited[i] = visited[x]+1
            dfs(i,y)
            
dfs(a,b)
print(visited[b])

bfs

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

n = int(input())
a, b = map(int, input().split())
m = int(input())

info = [[] for _ in range(n + 1)]
for _ in range(m):
    x, y = map(int, input().split())
    info[x].append(y)
    info[y].append(x)

visited=[-1]*(n+1)
def bfs(x, y):
    queue = deque()
    queue.append(x)
    visited[x] = 0
    while queue:
        x= queue.popleft()
        if x == y:
            return
        for i in info[x]:
            if (visited[i]==-1):
                queue.append(i)
                visited[i] = visited[x]+1
bfs(a,b)
print(visited[b])