[항해99] 99클럽 코테 스터디 10일차 TIL + BFS(백준 18352)

99클럽 코테 스터디 10일차 TIL + BFS(백준 18352)

오늘의 학습 키워드

• BFS
• 최단거리 알고리즘
• 단방향, 양방향
• 거리측정과 방문 체크

공부한 내용

1. 그래프의 방향성

• 이 문제에서는 단방향 그래프이기 때문에 양방향이랑 헷갈리지 않아야 한다.

for _ in range(M):
a, b = map(int, input().split())
graph[a].append(b) # 단방향

2. BFS를 이용한 최단 거리 찾기

• BFS의 deque를 활용하여 최단 거리를 찾는 방식
• 방문 리스트를 거리 저장 용도로 같이 활용한다면 더 효율적인 코드를 작성할 수 있다.

# 방문 배열을 거리 저장용으로 활용
visited = [-1] * (N + 1)  # -1로 초기화하여 미방문 표시
visited[start] = 0        # 시작점은 거리 0

# BFS while문 안에서
if visited[next_node] == -1:  # 미방문 노드 체크
    visited[next_node] = visited[current] + 1

3. 전체 코드

from collections import deque
import sys

input = sys.stdin.readline

N, M, K, X = map(int, input().split())
graph = [[] for _ in range(N + 1)]

# 단방향 그래프 생성
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)  # 단방향으로만 추가

visited = [-1] * (N + 1)  # 방문 배열을 거리 저장 용도로 활용

def BFS(start):
    queue = deque([start])
    visited[start] = 0  # 시작 도시까지의 거리는 0

    while queue:
        v = queue.popleft()

        for i in graph[v]:
            # 방문하지 않은 도시인 경우
            if visited[i] == -1:
                visited[i] = visited[v] + 1
                queue.append(i)

    # 거리가 K인 도시 찾기
    check = False
    for i in range(1, N + 1):
        if visited[i] == K:
            print(i)
            check = True

    if not check:
        print(-1)

BFS(X)

오늘의 회고

• 처음 문제를 풀 때 방문 리스트와 거리저장 리스트를 따로 두는 과정에서 문제 풀다가 스스로 혼동이 와서 어려움을 겪었다. 또 방향 그래프도 단방향인데 습관적으로 양방향으로 구현해서 풀어서 틀리기도 했다.
• 방문 리스트를 거리 저장용으로 함께 활용해서 더 효율적으로 구현하는데 익숙해져야하고 문제를 꼼꼼히 읽고 잘 구현해야 할 것 같다.