[백준] JavaScript - 숨바꼭질 (1697)

개요

문제 이름: 숨바꼭질 (1697)
문제 링크: https://www.acmicpc.net/problem/1697
플랫폼: 백준
알고리즘 분류: BFS
소요 시간: 1시간

 

문제 전문

설명

입출력

문제 풀이

해설

이 문제는 BFS(Breadth-First Search, 너비 우선 탐색) 알고리즘을 사용하여 해결할 수 있습니다. BFS는 그래프나 트리에서 인접한 노드를 먼저 탐색하는 알고리즘으로, 시작 노드에서 가까운 노드들을 먼저 방문하고 멀리 떨어진 노드를 나중에 방문합니다.

 

문제에서 수빈이는 현재 위치에서 걷거나 순간이동을 할 수 있습니다. 걸을 때는 X-1 또는 X+1로 이동하고, 순간이동을 할 때는 2*X의 위치로 이동합니다. 이를 그래프로 표현하면, 각 노드는 수빈이의 현재 위치를 나타내고, 각 노드에서 인접한 노드로의 간선은 걷거나 순간이동하는 경우를 나타냅니다.

 

BFS를 사용하여 시작 노드(수빈이의 초기 위치)에서부터 인접한 노드를 탐색하면서, 동생의 위치에 도달할 때까지 탐색을 진행합니다. 이때, 각 노드까지의 최단 시간을 기록하면서 탐색을 진행하면 동생을 찾는 가장 빠른 시간을 구할 수 있습니다.

 

문제를 요약하면 다음과 같습니다.

1. 수빈이의 초기 위치 N과 동생의 위치 K가 주어짐.
2. 수빈이는 현재 위치에서 걷거나 순간이동을 할 수 있음.
   1. 걷는 경우: X-1 또는 X+1로 이동 (1초 소요)
   2. 순간이동하는 경우: 2*X의 위치로 이동 (1초 소요)
3. 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 구해야 함.

 

그리고 상세한 풀이 방식은 다음과 같습니다.

1. 시작 노드(수빈이의 초기 위치)와 시간(0초)을 큐에 삽입합니다.
2. 큐가 빌 때까지 다음 과정을 반복합니다.
   1. 큐에서 현재 노드와 시간을 꺼냅니다.
   2. 현재 노드가 동생의 위치와 같다면, 현재 시간을 반환합니다.
   3. 현재 노드에서 인접한 노드(X-1, X+1, 2*X)에 대해 다음을 수행합니다.
      1. 인접한 노드가 범위 내에 있고, 아직 방문하지 않았다면...
         1. 인접한 노드를 방문 처리합니다.
         2. 인접한 노드와 현재 시간 + 1을 큐에 삽입합니다.

 

시도

1차 시도  (성공)

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split(" ").map(Number);
const [N, K] = input;

function bfs(start, target) {
	const queue = [[start, 0]];
	const visited = new Array(100001).fill(false);
	visited[start] = true;

	while (queue.length) {
		const [current, time] = queue.shift();

		if (current === target) {
			return time;
		}

		for (const next of [current - 1, current + 1, current * 2]) {
			if (next >= 0 && next <= 100000 && !visited[next]) {
				visited[next] = true;
				queue.push([next, time + 1]);
			}
		}
	}
}

console.log(bfs(N, K));

fs 모듈을 사용하여 표준 입력에서 데이터를 읽어옵니다.

1. fs 모듈을 사용하여 표준 입력에서 데이터를 읽어옵니다.
2. 구조 분해 할당을 사용하여 input 배열의 첫 번째 요소를 N에, 두 번째 요소를 K에 할당합니다.
   1. N은 수빈이의 초기 위치를 나타냅니다.
   2. K는 동생의 위치를 나타냅니다.
3. bfs 함수를 정의합니다. 이 함수는 시작 노드 start와 목표 노드 target을 매개변수로 받습니다.
   1. queue 배열을 초기화하고, 시작 노드와 시간(0초)을 배열로 묶어서 큐에 삽입합니다.
   2. visited 배열을 초기화하고, 모든 요소를 false로 채웁니다. 이 배열은 각 노드의 방문 여부를 저장합니다.
   3. 시작 노드의 방문 여부를 true로 설정합니다.
4. while 루프를 사용하여 큐가 빌 때까지 BFS를 수행합니다.
   1. queue.shift()를 사용하여 큐의 첫 번째 요소를 꺼내고, 현재 노드 current와 시간 time을 배열 구조 분해 할당을 통해 할당합니다.
   2. 현재 노드가 목표 노드와 같다면, 현재 시간을 반환하고 함수를 종료합니다.
5. for...of 루프를 사용하여 현재 노드에서 인접한 노드를 탐색합니다.
   1. 인접한 노드는 current - 1, current + 1, current * 2입니다.
   2. 각 인접한 노드 next에 대해 다음 조건을 확인합니다:
      1. next가 0 이상 100,000 이하의 범위 내에 있어야 합니다.
      2. visited[next]가 false여야 합니다. 즉, 아직 방문하지 않은 노드여야 합니다.
   3. 조건을 만족하는 인접한 노드에 대해 다음을 수행합니다:
      1. visited[next]를 true로 설정하여 방문 처리합니다.
      2. [next, time + 1]을 배열로 묶어서 큐에 삽입합니다. 이는 인접한 노드와 현재 시간에 1을 더한 값입니다.
6. bfs 함수를 호출하여 수빈이의 초기 위치 N과 동생의 위치 K를 전달하고, 반환된 결과를 콘솔을 사용하여 출력합니다.

 

사용된 주요 메서드

• Array.fill(value): 배열의 모든 요소를 지정된 값으로 채웁니다.
  • const visited = new Array(100001).fill(false);는 크기가 100001인 배열을 생성하고 모든 요소를 false로 초기화합니다.
• Array.shift(): 배열의 첫 번째 요소를 제거하고 그 요소를 반환합니다.
  • const [current, time] = queue.shift();는 큐의 첫 번째 요소를 제거하고, 현재 노드와 시간을 각각 current와 time 변수에 할당합니다.
• Array.push(element): 배열의 끝에 하나 이상의 요소를 추가하고, 배열의 새로운 길이를 반환합니다.
  • queue.push([next, time + 1]);는 인접한 노드와 시간 + 1을 큐의 끝에 추가합니다.

 

시간 복잡도 및 공간 복잡도

• 시간 복잡도: O(n)
  • 여기서 n은 최대 위치 값입니다. 각 노드는 최대 3번 방문될 수 있으므로(x-1, x+1, 2*x), 시간복잡도는 O(3n) = O(n)입니다.
• 공간 복잡도: O(n)
  • 방문 여부를 저장하는 배열 visited의 크기와 큐의 최대 크기가 n입니다.