[항해 99] 99클럽 코테 스터디 8일차 TIL + DFS(백준 2644)

99클럽 코테 스터디 8일차 TIL + DFS(백준 2644)

1. 오늘의 학습 키워드

• 백준 2644 촌수계산
• DFS

2. 공부한 내용 정리

2.1. 구현 내용

• 전체적인 구현 구조는 DFS의 기본 틀과 유사
• 그래프 구현: 인접 리스트를 사용하여 각 사람 간의 관계를 양방향으로 저장
• 방문 배열: visited 배열은 방문 체크와 동시에 촌수를 저장하는 용도로 사용
• DFS 구현:
  • 목표 노드 도달 시 현재까지의 촌수 반환
  • 연결된 노드들을 재귀적으로 탐색하며 촌수 계산
  • 경로가 없는 경우 -1 반환

2.2. 전체 코드

import sys
input = sys.stdin.readline

# 입력 받기
n = int(input())  # 전체 사람 수
a, b = map(int, input().split())  # 촌수를 계산해야 하는 두 사람
m = int(input())  # 부모-자식 관계의 개수
visited = [0] * (n+1)  # 방문 체크 및 촌수 저장 배열

# 그래프 초기화 및 관계 입력
graph = [[] for _ in range(n+1)]  # 인접 리스트로 그래프 표현
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)  # 양방향 그래프로 저장
    graph[y].append(x)

def DFS(v):
    if v == b:  # 목표 노드에 도달한 경우
        return visited[v]

    for i in graph[v]:  # 현재 노드와 연결된 모든 노드 확인
        if visited[i] == 0:  # 미방문 노드인 경우
            visited[i] = visited[v] + 1  # 촌수 증가
            result = DFS(i)  # 다음 노드로 재귀 탐색
            if result != -1:  # 목표 노드를 찾은 경우
                return result
    return -1  # 목표 노드를 찾지 못한 경우

visited[a] = 0  # 시작 노드 방문 표시
print(DFS(a))  # 결과 출력

3. 오늘의 회고

처음에는 단순히 DFS로 문제를 풀려고 했는데 촌수 계산을 어떻게 구현할지 고민하였다. 앞선 회차에서 풀었던 DFS와 유사하게 visited 배열을 단순 방문 체크가 아닌 촌수를 저장하는 용도로도 활용하는 아이디어를 적용하였다. 재귀 과정에서 이전 노드의 촌수에 +1을 저장하는 방식으로 구현하였다. DFS 문제가 아직 익숙치 않아 빠르게 구현하는데 어려움을 겪고 있는데 꾸준한 복습과 문제를 많이 풀어보는게 중요할 것 같다.