너비 우선 탐색(BFS) - 게임 맵 최단 거리 / 단어변환

게임 맵 최단 거리

게임 맵에서 시작점에서 목표 지점까지의 최단 거리를 찾는 문제

풀이 전략

1. 큐 초기화
   • 시작점 (0, 0)에서 BFS를 시작한다.
   • 큐에 [y좌표, x좌표, 거리]를 저장한다.
2. 탐색 진행
   • 큐에서 하나씩 꺼내 네 방향으로 이동 가능한 위치를 확인한다.
   • 벽이 아니고, 방문하지 않은 곳(maps[ny][nx] === 1)만 탐색한다.
   • 방문한 곳은 maps[ny][nx] = 0으로 설정해 다시 방문하지 않도록 한다.
3. 목표 지점 도달
   • 목표 지점 (n-1, m-1)에 처음 도달하면 distance 값을 반환한다.
4. 목표에 도달하지 못한 경우
   • 큐가 모두 비었을 때도 목표 지점에 도달하지 못하면 1을 반환한다.

function solution(maps) {
	const n = maps.length // 세로 길이
	const m = maps[0].length // 가로 길이

	// 방향 벡터
	const directions = [
		[-1, 0], [1, 0], [0, -1], [0, 1]
	] // 상, 하, 좌, 우

	// 1. BFS를 위한 큐 초기화 (시작점과 이동거리 저장)
	const queue = [[0, 0, 1]]; // [y, x, distance]

	// 2. BFS 탐색
	while(queue.length > 0) { // queue의 길이가 0 이상일 동안
		const [y, x, distance] = queue.shift(); // 큐에 저장된 값 가져오고 삭제

		// 3. 목표 지점에 도달했을 떄
		if(y === n - 1 && x === m - 1) return distance; // 거리 반환

		// 현재 위치에서 네 방향으로 이동
		for(const [dy, dx] of directions {
			const ny = y + dy;
			const nx = x + dx;

			// 맵을 벗어나지 않고 이동 가능한 곳이라면
			if(ny >= 0 && ny < n && nx >= 0 && nx < m && maps[ny][nx] === 1) {
				queue.push([ny, nx, distance + 1); // 큐에 추가
				maps[ny][nx] = 0; // 방문한 곳은 다시 방문하지 않도록 0으로 변경

			}

		}
	}

	// 4. BFS가 끝날 때까지 목표 지점에 도달하지 못한 경우
	return -1;

}

시간 복잡도

• 맵의 크기가 n x m일 때, BFS 탐색은 모든 칸을 한 번씩 방문하므로 O(n × m)의 시간 복잡도를 가진다.

공간 복잡도

• 큐를 사용하므로 O(n × m)의 공간이 필요하다.

---

단어 변환

각 단어를 그래프의 노드로 보고 한 번에 한 글자만 다른 단어를 간선으로 연결된 노드로 간주하여, 시작 단어 begin에서 목표 단어 target까지의 최단 경로를 BFS를 사용하여 찾는 문제

풀이 전략

1. 기본 조건 확인
   • target이 words에 없으면 변환할 수 없으므로 0을 반환한다.
2. 단어 변환 가능 여부 체크
   • 두 단어의 알파벳 차이가 1개인지 확인하는 isConvertible 함수를 정의한다.
3. BFS 탐색
   • 큐를 사용하여 시작 단어에서 변환 단계를 진행한다.
   • visited를 활용해 이미 방문한 단어를 재방문하지 않도록 처리한다.
4. 목표 단어 도달 시 반환
   • 목표 단어에 도달하면 변환 횟수를 반환한다.
5. 변환 불가능한 경우
   • BFS 탐색이 끝났음에도 target에 도달하지 못하면 0을 반환한다.

알고리즘 풀이

function solution(begin, target, words) {
	// 1. target이 words에 없으면 변환 불가
	if(!words.includes(target)) return 0;

	// 2. 단어 변환 가능 여부 체크 함수 정의
	const isConvertible = (word1, word2) => {
		let diff = 0; // 알파벳 차이

		for(let i = 0; i < word.length; i++) {
			if(word1[i] !== word2[i]) diff++;
			if(diff > 1) return false; // 차이가 1개 이상이면 false 반환
		}

		return diff === 1; // 차이가 1개인지 판별
	}

	const queue = [[begin, 0]]; // [현재 단어, 변환 횟수]
	const visited = new Set();

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

		// 목표 단어에 도달하면 변환 횟수 반환
		if(current === target) return count;

		for(const word of words {
			// 아직 방문하지 않았고, 단어 변환이 가능하다면
			if(!visited.has(word) && isConvertible(current, word)) {
					visited.add(word) // 방문 처리
					queue.push([word, count +1]); // 변환 후 큐에 추가
			}
		}
	}

	// BFS 탐색 후 target에 도달하지 못하면 변환 불가
	return 0;
}

시간 복잡도

• 단어 변환 체크: 두 단어의 길이가 l일 때, 변환 가능 여부를 확인하는 isConvertible 함수의 시간 복잡도는 O(l).
• BFS 탐색: 큐에 단어를 최대 n개 넣을 수 있으며, 각 단어에 대해 변환 가능 여부를 확인하므로 전체 시간 복잡도는 O(n × l).
  • 여기서 n은 words의 길이, l은 각 단어의 길이이다.

공간 복잡도

• BFS 큐와 방문 배열로 인해 공간 복잡도는 O(n).