공부한 내용 본인의 언어로 정리하기

백준_촌수계산

첫째줄 : 전체 사람의 수 n
둘째줄: 촌수를 계산해야하는 서로 다른 두사람의 번호
셋째줄 : 부모 자신들간의 관계의 개수 m
넷째줄 : 부모 자식간의 관계를 나타내는 두 번호 x,y(앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호)

• 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력

어떤 문제가 있었고, 나는 어떤 시도를 했는지

• 내가 생각한 방식 : dict 형태 (부모-key, 자식-value) 로 저장
• A와 B 사이의 관계를 알고 싶을 때 DFS의 경우 모든 경우를 고려해야 될 수도 있지만, BFS는 가까운 관계부터 탐색을 할 수 있습니다. (참고) -> BFS 로 구현

내가 제출한 풀이

import sys
from collections import deque

# 입력을 위한 readline 사용
input = sys.stdin.readline

# 정수 입력
n = int(input().strip())
num1, num2 =  map(int,input().split())
m = int(input().strip())

visited =[False] *(n+1)
arr =[[] for _ in range(n+1)]

for i in range(m):
    a, b = map(int, input().split()) 
    arr[a].append(b)
    arr[b].append(a)
depth =-1

# BFS를 사용하여 두 노드 간의 촌수를 찾는 함수
def bfs(start, end):
    global depth
    queue = deque([(start, 0)])  # 노드와 깊이를 큐에 저장
    visited[start] = True

    while queue:
        current, d = queue.popleft()

        if current == end:
            depth = d
            return

        for neighbor in arr[current]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append((neighbor, d + 1))

        
# 시작 노드와 끝 노드로 BFS 수행
bfs(num1, num2)
print(depth)

DFS 이용한 풀이

• 다른 분들의 풀이를 보니까 'DFS' 로 접근하신 분이 많았다.
• 위와 동일하지만, dep 를 추가하여 호출될때마다 갱긴해나갔다

def dfs(current,end,dep):
    global depth
    if current == end:
        if depth==-1 or dep<depth:
            depth =dep
        return
    
    visited[current] =True
    for n in arr[current]:
        if not visited[n]:
            dfs(n,end,dep+1)
    visited[current] = False

dfs(num1,num2,0)
print(depth)
    

무엇을 새롭게 알았는지

• 언제 dfs, bfs 를 적용해야하는지 알게되었다

학습할 것은 무엇인지

• dfs, bfs 여러 사례 풀기