bfs(js)

BFS 알고리즘은 그래프나 트리에서 두 노드 사이의 최단 거리를 구하거나, 미로 찾기 등에서 사용할 수 있는 대표적인 그래프 탐색 알고리즘입니다. BFS 알고리즘을 사용할 수 있는 대표적인 문제 유형은 다음과 같습니다.

1. 최단 거리 구하기

   • 출발점에서 도착점까지의 최단 경로를 구하는 문제
   • 대표적으로 백준 2178번 미로 탐색 문제가 있습니다.

2. 연결 요소(Connected Component) 구하기

   • 무방향 그래프에서 서로 연결된 부분들을 구하는 문제
   • 대표적으로 백준 11724번 연결 요소의 개수 문제가 있습니다.

3. 트리 지름 구하기

   • 트리에서 가장 먼 두 노드 사이의 거리를 구하는 문제
   • 대표적으로 백준 1167번 트리의 지름 문제가 있습니다.

4. 숨바꼭질

   • 그래프에서 특정 위치까지 최소 시간으로 이동하는 문제
   • 대표적으로 백준 1697번 숨바꼭질 문제가 있습니다.

5. 그 외

   • 그래프에서 최소 비용으로 이동하는 문제 등 다양한 문제에서 활용할 수 있습니다.

   각각의 유형에 대해 문제와 함께 설명드리겠습니다.

6. 최단 거리 구하기

• 문제 링크: https://www.acmicpc.net/problem/1697
• 문제 설명: 한 점에서 출발하여 다른 점으로 가는 최단 거리를 구하는 문제입니다. 이 문제에서는 1차원 배열 상에서 이동하는 문제입니다.
• 풀이 방법: BFS를 사용하여 최단 거리를 구합니다. 한 점에서 다른 점으로 가는 최단 거리를 구하므로 BFS를 이용하면 됩니다. 큐에 현재 위치와 이동한 거리를 함께 넣어주어 해당 위치에서 다른 위치로 이동한 거리를 구합니다.

2. 연결 요소(Connected Component) 구하기

• 문제 링크: https://www.acmicpc.net/problem/11724
• 문제 설명: 연결 요소란 그래프 상에서 서로 연결된 정점들의 집합을 의미합니다. 이 때, 그래프 상에서 연결되어 있지 않은 정점들은 각각 별개의 연결 요소를 이루게 됩니다. 이 문제에서는 무방향 그래프가 주어지고, 연결 요소의 개수를 구하는 문제입니다.
• 풀이 방법: BFS나 DFS를 사용하여 각 정점을 방문하면서 연결된 정점들을 탐색합니다. 이 때, 이미 방문한 정점은 다시 탐색하지 않도록 방문 여부를 체크해주어야 합니다. 모든 정점을 방문할 때까지 BFS나 DFS를 반복하며 연결 요소의 개수를 구합니다.

3. 트리 지름 구하기

• 문제 링크: https://www.acmicpc.net/problem/1967
• 문제 설명: 무방향 트리가 주어질 때, 가장 긴 경로의 길이를 구하는 문제입니다. 이 때, 경로의 길이는 경로 상의 간선 가중치의 합입니다.
• 풀이 방법: 트리에서 루트 노드를 임의로 설정한 후, 가장 거리가 먼 노드를 찾습니다. 그 노드를 기준으로 다시 가장 거리가 먼 노드를 찾습니다. 이 때, 두 노드 사이의 거리가 트리의 지름입니다. 이를 위해 BFS를 사용하면 됩니다.

4. 숨바꼭질

• 문제 링크: https://www.acmicpc.net/problem/1697
• 문제 설명: 한 점에서 출발하여 다른 점으로 가는 최단 거리를 구하는 문제입니다. 이 문제에서는 1차원 배열 상에서 이동하는 문제입니다. 하지만, 이

숨바꼭질 문제는 어떤 지점에서 다른 지점으로 가는 최단 거리를 찾는 문제로, 특히 BFS 알고리즘을 이용해 풀 수 있는 대표적인 문제 중 하나입니다.

문제에서는 N개의 수물장터가 있고, 그 중에는 동생이 숨어있습니다. 수물장터들은 양방향 도로로 연결되어 있으며, 동생이 있는 장소는 고정되어 있습니다. 동생이 숨어있는 수물장터의 번호와 출발 지점의 번호가 주어졌을 때, 출발 지점에서 동생이 있는 지점으로 가는 최단 거리를 구하는 문제입니다.

BFS 알고리즘을 이용하여 출발 지점에서부터 동생이 숨어있는 지점으로 가는 최단 거리를 구할 수 있습니다. 출발 지점에서부터 시작해서, 인접한 노드들을 큐에 넣고 방문 처리를 하면서 순차적으로 탐색을 진행합니다. 이 때, 방문한 노드의 거리를 기록하고, 동생이 숨어있는 지점을 방문했을 때, 그 때의 거리를 반환하면 됩니다.

구체적인 풀이 과정은 다음과 같습니다.

1. 출발 지점에서부터 BFS 탐색을 시작합니다.
2. 큐에 출발 지점을 넣고, 방문 처리를 합니다.
3. 큐가 빌 때까지 반복합니다.
4. 큐에서 노드를 하나 꺼내서 인접한 노드들을 큐에 넣습니다. 이 때, 인접한 노드가 방문하지 않은 노드이면 방문 처리를 하고, 큐에 넣습니다.
5. 방문한 노드가 동생이 숨어있는 지점이면, 그 때의 거리를 반환합니다.
6. 큐가 빌 때까지 동생이 숨어있는 지점을 찾지 못한 경우, -1을 반환합니다.

아래는 숨바꼭질 문제를 BFS 알고리즘을 이용해 푼 구체적인 JavaScript 코드입니다.

function solution(N, K) {
    const visited = new Array(100001).fill(false);
    const queue = [];
    queue.push([N, 0]); // 출발지점과 거리
    visited[N] = true; // 방문처리
    
    while (queue.length) {
        const [current, distance] = queue.shift();
        if (current === K) { // 동생이 있는 지점에 도달한 경우
            return distance;
        }
        // 인접한
      ```