99클럽 코테 스터디 5일차 TIL: BFS

문제

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

풀이

문제 이름에서 나와있는대로 BFS를 구현하는 문제이다.
BFS는 많이 풀어봤던 문제이고 로직 또한 익숙했다.

문제에서 무방향 그래프로 나타나있어서, 인접행렬 혹은 인접리스트로 구현할 때 처리를 해주어야 했다.
추가로 오름차순 순으로 방문해야 하기 때문에, 정렬이 필요했다.

BFS는 Queue 자료구조를 사용하는데, Queue에 넣을 때 방문한 순서를 1증가시켜 주었다.
또한 visited 배열을 방문한 순서를 들고 있도록 하기 위해 Int 배열로 만들어주었다.
여기서 visited[i] = 0 이면 미방문 노드이고, 2라면 2번째 순서로 방문한 노드와 같이 생각하면 된다.

문제에서 방문하지 못하는 노드의 순서는 0으로 처리하라고 되어있어서 그 부분 처리도 가능하다.

일단 문제는 풀었다.
다만 문제에 나와있는 슈도코드 중에 이해가 잘 가지 않는 부분이 있었다.
for each v ∈ V - {R}

해당 부분은 visited 배열을 초기화 하는 부분인 것 같은데..

이해가 안가서 GPT한테 물어봤다..

아하 첫번째 노드를 제외하고 나머지 노드를 방문처리 해주는 코드였다.

소스코드

후기

BFS를 사용하는 간단한 문제였다.