프로그래머스 JS 깊이/너비 우선 탐색(DFS/BFS) [4/7]
단어 변환(lv3) 문제 보기 (25)
문제 풀이
고려해야할 문제의 조건은 세가지다.
- 한번에 한개의 알파벳 변경 가능
- words에 존재하는 단어로만 변환 가능
- 중복되는 단어 없음
목표는
words 배열의 길이만큼 변환 시도를 했을 때, 변환할 수 없다면 0을 반환하고,
변환이 가능하다면 최소 변환 횟수를 구하는 것이다.
1. words 배열의 길이만큼 변환 시도를 한다.
words.forEach((word, index) => {
});2. 단어 변환이 가능한지 확인한다.
하나의 알파벳만이 다르면 변환이 가능하기 때문에 몇 개의 알파벳이 일치하는지 확인하면 된다.
words.forEach((word, index) => {
let sameCount = 0;
for (let i = 0; i < wordLength; i++) {
if (word[i] === compareWord[i]) {
sameCount++;
}
}
});3.
단어 변환이 가능하면 해당 단어로 변환한다, 변환된 단어는 방문처리 한다, count +1을 한다
변경 사항을 dfs에 전달한다.
변환 전 상태로 되돌린다.
words.forEach((word, index) => {
//... const sameCount = getSameCount()
if (sameCount === wordLength - 1) {
compareWord = word;
words[index] = "";
dfs(words, compareWord, count + 1);
compareWord = begin;
words[index] = word;
}
});4. target으로 변환했다면 count를 반환한다.
if (compareWord === target) {
result = Math.min(count, result);
return;
}전체 코드
타겟 넘버(lv2) 문제 보기 (5)
문제 풀이
numbers의 각 자리에 대하여 각각 한번씩 +, -을 한 결과를 만들면 된다.
0 으로 시작하여, numbers[i] 번째까지 확인하도록 하려면 어떻게 해야할지 생각하면 된다.
1. numbers의 길이만큼 더하거나 뺐다면 재귀를 더이상 실행하지 않도록 한다.
2. i회 만큼 더하거나 뺀 수의 결과가 target 과 같다면 count를 ++ 한다.
3. 0에서 시작하여 0 (+ or -) numbers[i] 를 한 다음 numbers[i]를 더하거나 뺄 수 있도록 i +1 을 해준다.
function solution(numbers, target) {
const numbersLength = numbers.length;
let count = 0;
const dfs = (number, i) => {
if (i === numbersLength) {
if (number === target) {
count++;
}
return;
}
dfs(number + numbers[i], i + 1);
dfs(number - numbers[i], i + 1);
};
dfs(0, 0);
return count;
}게임 맵 최단거리(lv2) 문제 보기 (10)
문제 해결
다음으로 이동 가능한 좌표는 상, 하, 좌, 우 넷 중에 하나이다.
이동 가능한 좌표가 1이면 이동을 할 수 있다.
=> 게임 보드 안에서 상하좌우 중에서 좌표가 1인 경우에 이동한다.
const canMove = (xMove, yMove, n, m, maps) => {
return xMove >= 0 && yMove >= 0 && xMove < n && yMove < m && maps[xMove][yMove] === 1;
};
방문한 좌표는 1에서 0으로 바꾸어 준다.
문제를 해결하기 위해서는 queue를 이용하여야 한다
stack을 이용하였을 때와 queue를 이용하였을 때 차이를 설명하자면,
1 : 다음으로 이동가능한 좌표
[
[ 0, 0, 1, 1, 1 ],
[ 0, 0, 1, 0, 1 ],
[ 0, 0, 1, 1, 1 ],
[ 0, 0, 1, 0, 1 ],
[ 0, 0, 0, 0, 1 ]
]
[
[ 0, 0, 1, 1, 1 ],
[ 0, 0, 1, 0, 1 ],
[ 0, 0, 1, 1, 1 ],
[ 0, 0, 0, 0, 1 ],
[ 0, 0, 0, 0, 1 ]
]
[
[ 0, 0, 1, 1, 1 ],
[ 0, 0, 1, 0, 1 ],
[ 0, 0, 0, 1, 1 ],
[ 0, 0, 0, 0, 1 ],
[ 0, 0, 0, 0, 1 ]
]
이 분기에서 dfs라면 위쪽 경로를 먼저 선택했을 때, p가 먼저 최종 목표에 도달한다.
오른쪽 경로가 출발했을 때는 이미 방문처리된 (2,4)로 인해 이동할 수 없게 되고,
결국 최단거리가 아니게 된다.
[
[ 0, 0, 1, 1, 1 ],
[ 0, 0, 0, 0, 1 ],
[ 0, 0, 0, 0, 1 ],
[ 0, 0, 0, 0, 1 ],
[ 0, 0, 0, 0, 1 ]
]
하지만 bfs라면 위쪽 경로와 오른쪽 경로를 함께 탐색하여
오른쪽을 선택한 경로가 위쪽으로 탐색하려는 경로보다 우선하여 (2,4)를 지나가게 되고,
최종 목적지에 도달하는 것은 오른쪽을 선택한 경로가 되어 최단거리를 구할 수 있게 된다.
const canMove = (xMove, yMove, n, m, maps) => {
return xMove >= 0 && yMove >= 0 && xMove < n && yMove < m && maps[xMove][yMove] === 1;
};
function solution(maps) {
const [n, m] = [maps.length, maps[0].length]; // 보드 크기
const p = [0, 0, 0]; // 플레이어의 x좌표, y좌표, 이동 횟수
const moveQueue = [p]; // 초기 플레이어의 좌표 설정
const dirs = [
[-1, 0], // 상
[1, 0], // 하
[0, -1], // 좌
[0, 1], // 우
];
// 이동이 불가능할 때까지 시행합니다.
while (moveStack.length) {
const [x, y, count] = moveStack.shift(); // queue를 사용하지 않으면 항상 최단거리가 아니게 된다.
// p의 좌표가 목적지에 위치해 있다면 이동 횟수를 반환하여 게임을 종료합니다.
if (x === n - 1 && y === m - 1) {
return count + 1;
}
for (let dir of dirs) {
const [dx, dy] = dir;
const xMove = x + dx;
const yMove = y + dy;
// 다음으로 이동가능한 좌표가 존재할 경우
if (canMove(xMove, yMove, n, m, maps)) {
// 해당 좌표로 이동
maps[xMove][yMove] = 0; // 방문 표시 남기기
moveQueue.push([xMove, yMove, count + 1]);
}
}
}
// 최종 목적지에 도달하지 못했다면 -1을 반환합니다.
return -1;
}네트워크(lv3) 문제 보기 (60)
문제 해결
1. 각각의 컴퓨터에 연결된 네트워크를 기록한다.
{
'0': [ 1 ],
'1': [ 0, 2 ],
'2': [ 1 ]
}
2. 처음에는 모든 네트워크가 끊어져 있다고 가정한다.
let count = n;
3. n번째 컴퓨터와 연결되어 있는 네트워크 수 만큼 count-- 를 해주면 총 네트워크 수를 확인할 수 있다.
확인하는 컴퓨터와, 다음으로 연결할 컴퓨터의 방문처리를 신경써주면 된다.
아래 설명을 보면 쉽게 이해할 수 있을 것이다.
ex1)
[
[1,1,0],
[1,1,0],
[0,0,1]
]
1번째가 2번째가 연결
3번째는 연결 X
let count = 3;
1번째 컴퓨터 확인 => 1번째 컴퓨터 방문처리 => 2번째와 연결되어 있음 => 2번째 방문처리 => count = 2
2번째 컴퓨터 확인 => 1번째와 연결되어 있으나 이미 방문처리 되어 있음 => 더 이상 연결된 컴퓨터 없음 count = 2
3번째 컴퓨터 확인 => 연결된 컴퓨터가 없음 => count = 2
총 네트워크 수는 2개가 된다.
ex2)
[
[1,1,0,0],
[1,1,0,0],
[0,0,1,1],
[0,0,1,1],
]
1번째와 2번째가 연결
3번째와 4번째가 연결
let count = 4;
1번째 확인 => 1번째 방문처리 => 2번째와 연결되어 있음 => 2번째 방문처리 => count = 3
2번째 확인 => 1번째와 연결되어 있으나 이미 방문처리 되어 있음 => 더 이상 연결 없음 count = 3
3번째 확인 => 3번째 방문처리 => 4번째와 연결되어 있음 => 4번째 방문처리 => count = 2
4번째 확인 => 3번째와 연결되어 있으나 이미 방문처리 되어 있음 => 더 이상 연결 없음 count = 2
const solution = (n, computers) => {
const obj = {}; // 각각의 컴퓨터와 연결된 네트워크를 기록
const visited = Array.from({ length: n }).fill(0);
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
// 자기 자신은 항상 1이므로 제외
if (i === j) continue;
// i번째 컴퓨터와 연결된 컴퓨터의 index기록
if (computers[i][j]) {
obj[i] = obj[i] ? [...obj[i], j] : [j];
}
}
}
let count = n; // 처음엔 모든 네트워크가 끊겨있다고 가정하고,
// 각각의 컴퓨터를 확인
for (let i in obj) {
const queue = [...obj[i]];
visited[i] = 1; // i번째 네트워크 방문처리
// 연결된 네트워크가 있을 때
while (queue.length) {
const next = queue.shift();
// 방문하지 않은 네트워크라면
if (!visited[next]) {
visited[next] = 1; // 다음번 네트워크 방문처리
queue.push(...obj[next]); // 해당 컴퓨터와 연결된 네트워크들을 추가
count--; // 네트워크 연결
}
}
}
return count;
};