BFS
사용처
최단거리를 찾을 때 주로 사용한다. 또는 동시에 진행하면서 비교를 해야하는 문제에 적합하다.
구조
const BFS=()=>{
while(!queue.length){
let [x,y]=queue.shift();
//반복문+조건문(지나온 곳 접근 방지)
queue.push([x,y]);
}
}tip
시작점이 명확할 때는 큐에 지점과 카운트할 값을 넣어두고 큐가 끝날 때까지 반복한다.
시작점이 바뀌어야 하는 경우 반복문을 하나 더 감싸주고 경우에 따라 방문 표시를 초기화해준다.
특정 거리의 도시 찾기
문제
도시 개수, 거리정보, 출발도시, 연결된 도로의 배열를 이용해 출발도시 start에서 k의 거리에 있는 도시의 개수를 구하여라.
접근방법
BFS
1. 각 도시에 연결된 도로 정보를 Map을 통해 저장하고(key:[]의 형태)
2. 시작 도시를 큐에 넣은 뒤
3. 각 도시를 순회하며 연결된 도시로 이동해 거리를 측정함
javascript 오답 코드
내가 작성한 코드는 다음과 같다. 백준 불통...
const solution = (n, m, k, start, roads) => {
const queue = [];
const visited = Array(n).fill(false);
const linked = new Map();
const answer = [];
for (let i = 0; i < n; i++) {
linked[i + 1] = [];
}
//연결된 도시 저장
for (let i = 0; i < roads.length; i++) {
linked[roads[i][0]].push(roads[i][1]);
}
//start부터 queue에 넣어줌
queue.push([linked[start], 1]);
visited[start - 1] = true;
//연결된 도시들 모두 방문
while (queue.length) {
let [cities, d] = queue.shift();
while (cities.length) {
let now = cities.shift();
//1->3 루트로 방문헀다면 1->2->3루트로 방문하는 일이 없도록 continue해줌
if (visited[now - 1]) continue;
visited[now - 1] = true;
if (d === k) answer.push(now);//정답 추가
queue.push([linked[now], d + 1]);
}
if(d===k) break;
}
answer.sort((a, b) => a - b);
if (answer.length){ console.log(answer.join("\n"));}
else console.log("-1");
};정답 코드
const solution = (n, m, k, start, roads) => {
const queue = [];
const visited = Array(n+1).fill(0);//0이면 방문x, 그외는 방문o
const linked = Array.from(Array(n + 1), () => []);
const answer = [];
for (const [s, d] of roads) {
linked[s].push(d);
}
queue.push(start);
visited[start] = 1;
while (queue.length) {
let cur = queue.shift();
//거리가 k+1에 해당한다면 정답 처리
if (visited[cur] === k + 1) {
answer.push(cur);
continue;
}
//연결도시들을 돌며 방문하지 않았다면 queue에 추가하고 방문처리함.
for (const next of linked[cur]) {
if (visited[next] === 0) {
queue.push(next);
visited[next] = visited[cur] + 1;
}
}
}
answer.sort((a, b) => a - b);
if (answer.length) {
console.log(answer.join("\n"));
} else console.log("-1");
};
Array.from 메서드
Array.from은 문자열 등의 유사 배열(Array-like) 객체나 이터러블한 객체를 배열로 만들어주는 메서드이다.
Array.from(Array(n + 1), () => []);//array를 n+1개의 []로 채움
//결과 : [ [], [ 2, 3 ], [ 3, 4 ], [], [] ]히든 케이스
4 3 1 1
2 1
3 1
4 1
answer:-1
4 3 2 4
4 3
3 2
2 1
answer:2
게임 맵 최단거리
문제
5X5 맵에서 (0,0)->(5,5)를 최단 거리로 갈 수 있는 방법을 구하여라.
정답 코드
// 상 우 하 좌
const DIRECTION = [[1, 0], [0, 1], [-1, 0], [0, -1]];
// BFS 활용
function solution(maps) {
const row = maps.length - 1, col = maps[0].length - 1;
// 큐 - 시작 위치 y, x, 이동 거리
const queue = [[0, 0, 1]];
while(queue.length) {
// 큐 추출
let [y, x, count] = queue.shift();
// 상대 팀 진영이라면
if(y === row && x === col) return count;
// 동서남북 확인
for(let i = 0; i < 4; i++) {
const [dy, dx] = DIRECTION[i];
const [nextY, nextX] = [dy + y, dx + x];
// 맵 밖으로 나간다면
if(nextY < 0 || nextX < 0 || nextY > row || nextX > col) continue;
// 도착한 곳이 벽이라면
if(maps[nextY][nextX] === 0) continue;
// 이미 지난 곳 벽으로 만들어서 다음에 접근 방지
maps[nextY][nextX] = 0;
// 다음에 확인해야하는 곳 큐에 추가
// 갈수 있는 곳이 두 곳이라면 두 곳 추가됨
queue.push([nextY, nextX, count + 1]);
}
}
return -1;
}틀린 풀이 : DFS
DFS로 최단 거리를 구하는 방식은 너무 비효율적이다. 동시에 진행하면서 빨리 도착하는 말을 최소값으로 정하는 게 아니라 모든 값을 구한 후 최소값을 정하기 때문이다. 깊이 우선 탐색은 완전 탐색에 더 적절하다.
function solution(maps) {
var answer = 0;
let min = 100;
const DFS = (x, y, cnt) => {
if (x === 4 && y === 4) {
min = Math.min(min, cnt);
} else {
if (maps[x][y] === 1) {
// cnt++;
console.log(y+1,x+1)
maps[x][y] = 0;
if (x <= 3) {
DFS(x + 1, y, cnt + 1);
}
if (y <= 3) {
DFS(x, y + 1, cnt + 1);
}
if (x >= 1) DFS(x - 1, y, cnt + 1);
if (y >= 1) DFS(x, y - 1, cnt + 1);
} else {
return;
}
}
return min;
};
answer = DFS(0, 0, 1);
return answer === 100 ? -1 : answer;
}
//결과
[
[ 3, 0, 13, 12, 11 ],
[ 2, 0, 14, 0, 10 ],
[ 3, 0, 7, 8, 9 ],
[ 4, 5, 6, 0, 10 ],
[ 0, 0, 0, 0, 1 ]
]출처 : 프로그래머스
