BFS 접근 방식

문제

프로그래머스 숫자변환하기

https://school.programmers.co.kr/learn/courses/30/lessons/154538

1. 문제 분석

• 주어진 수식의 연산 우선순위를 조정하여 최대의 결과값을 찾는 것
• 목표는 가능한 모든 연산자 우선순위를 조합하여 결과를 계산하고, 그 중에서 최대값을 찾는 것이다.

2. 알고리즘 선택

• ‘x를 y로 변환하기 위해 필요한 최소 연산 횟수’ 부분에서 BFS으로 접근 판단

1차 풀이 - 시간초과

function solution(x: number, y: number, n: number) {
	const queue: [number, number][] = [];
	const visited = new Set();

	queue.push([x, 0]);
	visited.add(x);

	while (queue.length > 0) {
		const [x, count] = queue.shift()!;
		if (x === y) return count;

		const nextNumbers = [x + n, x * 2, x * 3];

		for (const num of nextNumbers) {
			if (visited.has(num) || num > y) continue;
			queue.push([num, count + 1]);
			visited.add(num);
		}
	}

	return -1;
}

• BFS 상향식 접근

2차 풀이

function solution(x: number, y: number, n: number) {
	const queue: [number, number][] = [];
	const visited = new Set();

	queue.push([y, 0]);
	visited.add(y);

	while (queue.length > 0) {
		const [current, count] = queue.shift()!;
		if (current === x) return count;

		const nextNumbers = [];
		if (current % 2 === 0) nextNumbers.push(current / 2);
		if (current % 3 === 0) nextNumbers.push(current / 3);
		nextNumbers.push(current - n);

		for (const num of nextNumbers) {
			if (visited.has(num) || num < x) continue;
			queue.push([num, count + 1]);
			visited.add(num);
		}
	}

	return -1;
}

• BFS 하향식 접근

두 접근 방식이 차이가 나는 이유

1. 상태 공간의 크기
   1. 하향식 접근은 목표 숫자 y에서 시작하여 숫자를 줄여 나가므로 탐색할 범위가 작고 불필요한 상태를 빠르게 배제
   2. 상향식 접근은 시작 숫자 x에서 목표 숫자 y로 가는 경로를 탐색하기 때문에 상태 공간이 넓어지고, 목표 숫자 y를 넘어서야 하는 경우 발생 가능
2. 연산의 방향과 효율성
   1. 하향식 접근은 역방향 연산 (예: 나누기, 빼기)을 사용하여 목표 숫자에 가까운 상태에서 시작하므로, 연산의 효율이 높음
   2. 상향식 접근은 전방향 연산 (예: 더하기, 곱하기)을 사용하여 숫자를 증가시키기 때문에 많은 상태를 생성

결론

하향식 접근 방식이 상태 공간이 상대적으로 작아 효율적이며, 상향식 접근은 상태 공간이 넓어 비효율적일 수 있다.