BFS는 어떤 알고리즘인가?
BFS는 breadth-first-search의 줄임말로, 그래프에서 너비를 우선으로 탐색하는 알고리즘이다.
DFS는 한 경로를 끝까지 파고 들어가지만, BFS는 현재 위치에서 가까운 요소들을 우선적으로 탐색한다.
만약 위의 그래프를 BFS로 탐색한다면 2 -> 7 -> 5 -> 2 -> 6 -> 9 -> 5 -> 11 -> 4의 순서로 탐색하게 될 것이다.
BFS는 어떤 상황에 쓰이는가?
BFS는 항상 가까운 요소부터 탐색하기 때문에 최단 경로를 구할 때 많이 쓰인다.
모든 요소를 다 탐색하지 않고도 가장 가까운 거리/횟수로 특정 요소를 찾아야 할 때 유용하다.
BFS는 어떻게 구현하는가?
BFS는 큐를 이용해 구현할 수 있다.
큐는 가장 먼저 들어온 요소가 가장 먼저 탐색되는(FIFO) 자료구조이기 때문에, 가까운 요소를 먼저 탐색해야 하는 BFS의 성질과 동일하다.
shift()로 맨 앞의 요소를 꺼내 탐색하고, 연결된 요소는 push()로 맨 뒤에 추가한다.
또한, DFS와 동일하게 방문 여부를 체크하여 이미 방문한 곳은 재방문 하지 않도록 한다.
function bfs(start) {
const queue = [];
queue.push(start);
visited[start] = true;
while (queue.length) {
const cur = queue.shift();
for (const next of graph[cur]) {
if (!visited[next]) {
visited[next] = true;
queue.push(next);
}
}
}
}관련 문제 풀어보기
[백준] 알고스팟
- 난이도 : 골드 4
- 문제 링크 : https://www.acmicpc.net/problem/1261
BFS로 보드를 전부 순환하며 벽 개수를 세서 마지막 위치에 도달했을 때 가장 적은 벽 개수를 반환하도록 하려고 했는데 일반 BFS로 풀면 시간 초과가 발생했다.
이 문제를 일반 BFS로 풀면 안 되는 이유는 이동하는 비용이 다르기 때문이다.
빈 방은 비용이 0이지만 벽은 비용이 1이다.
일반 BFS는 모든 비용이 동일할 때만 최단 거리를 보장한다. (최단 경로 도착 !== 최소 벽 개수)
const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const [M, N] = input.shift().split(' ').map(Number);
const board = input.map(i => i.split('').map(Number));
const visited = Array.from({length: N+1}, () => Array(M+1).fill(false));
const move = [[0,1], [0,-1], [-1,0], [1,0]];
let answer = M * N;
const queue = [];
queue.push([0,0,0]);
while(queue.length){
const [x,y,count] = queue.shift();
visited[x][y] = true;
if(x === N - 1 && y === M - 1 && count < answer){
answer = count;
}
for(let [dx, dy] of move){
const nx = x+dx;
const ny = y+dy;
if(nx >= 0 && nx < N && ny >= 0 && ny < M && !visited[nx][ny]){
queue.push([nx, ny, count+Number(board[nx][ny])]);
}
}
}
console.log(answer);이런 경우에는 비용이 적은 것을 먼저 처리하고, 비용이 많은 것을 나중에 처리하면 가장 적은 비용으로 도달하는 경우를 빠르게 구할 수 있다.
이를 위해 덱을 이용한다. (비용이 0인 경우 앞에 넣고, 1인 경우 뒤에 넣기 -> 맨 앞부터 꺼내서 처리)
또한, 단순히 좌표의 방문 여부를 처리하는 것이 아닌 좌표별 최소 비용을 저장하도록 한다.
이때 최소 비용을 보장하기 위해 예정되는 비용(dist[x][y] + board[nx][ny])이 원래 비용(dist[nx][ny])더 낮을 경우에만 deque에 값을 추가한다.
const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const [M, N] = input.shift().split(' ').map(Number);
const board = input.map(i => i.split('').map(Number));
const dist = Array.from({ length: N }, () => Array(M).fill(Infinity));
const move = [[0,1], [0,-1], [-1,0], [1,0]];
const deque = [];
deque.push([0,0]);
dist[0][0] = 0;
while(deque.length){
const [x,y] = deque.shift();
for(let [dx, dy] of move){
const nx = x+dx;
const ny = y+dy;
if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
const cost = dist[x][y] + board[nx][ny];
if(cost < dist[nx][ny]){
dist[nx][ny] = cost;
if(board[nx][ny] === 0){
deque.unshift([nx,ny])
}else{
deque.push([nx,ny])
}
}
}
}
console.log(dist[N-1][M-1]);[백준] 미로 만들기
- 난이도 : 골드 4
- 문제 링크 : https://www.acmicpc.net/problem/2665
위의 문제랑 벽/빈 방 숫자만 반대일뿐 동일하므로 빈 방을 0, 벽을 1로 반전시켜서 최소 벽 개수를 구한다.
const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const N = +input.shift();
const board = input.map(i => i.split('').map(n => 1 - +n));
const move = [[0,1], [0,-1], [-1,0], [1,0]];
const dist = Array.from({length: N}, () => Array(N).fill(Infinity));
const deque = [];
deque.push([0,0]);
dist[0][0] = 0;
while(deque.length){
const [x,y] = deque.shift();
for(let [dx,dy] of move){
const nx = x+dx;
const ny = y+dy;
if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
const cost = dist[x][y] + board[nx][ny];
if(cost < dist[nx][ny]){
dist[nx][ny] = cost
if(board[nx][ny] === 0){
deque.unshift([nx,ny])
}else{
deque.push([nx,ny])
}
}
}
}
console.log(dist[N-1][N-1]);[백준] 주난의 난
- 난이도 : 골드 4
- 문제 링크 : https://www.acmicpc.net/problem/14497
- 위치에서 시작해서 #에 도달할 때까지 상하좌우로 인접한 1을 모두 0으로 만든다.
이때 중요한 점은 0은 통과하기 때문에 1을 만날 때까지 파장이 커진다는 점이다.
즉, 0은 이동 비용이 0이고 1은 이동 비용이 1이다.
이동 비용이 동일하지 않기 때문에 위의 문제와 마찬가지로 일반 BFS로 풀면 안 되고, 각 좌표별 거리를 저장해야 한다.
0인 부분을 먼저 탐색하기 위해 다음 값이 0일 경우 앞에 넣고, 1일 경우 뒤에 넣는다. (덱 필요)
const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const [N,M] = input[0].split(' ').map(Number);
const [X1,Y1,X2,Y2] = input[1].split(' ').map(Number);
const move = [[0,1], [0,-1], [-1,0], [1,0]];
const dist = Array.from({length: N}, () => Array(M).fill(Infinity));
const board = [];
for(let i=2;i<2+N;i++){
const row = [];
for(let j=0;j<M;j++){
if(input[i][j] === "#" || input[i][j] === "1"){
row.push(1)
}else{
row.push(0)
}
}
board.push(row)
}
const deque = [];
deque.push([X1-1,Y1-1]);
dist[X1-1][Y1-1] = 0;
while(deque.length){
const [x,y] = deque.shift();
for(let [dx,dy] of move){
const nx = x+dx;
const ny = y+dy;
if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
const cost = dist[x][y] + board[nx][ny];
if(cost < dist[nx][ny]){
dist[nx][ny] = cost
if(board[nx][ny] === 0){
deque.unshift([nx,ny])
}else{
deque.push([nx,ny])
}
}
}
}
console.log(dist[X2-1][Y2-1])[백준] 게임
- 난이도 : 골드 5
- 문제 링크 : https://www.acmicpc.net/problem/1584
문제 분석
- 구역 종류
- 죽음 (진입 x)
- 위험 (생명-1)
- 안전
- 항상 (0,0)에서 출발하여 (500,500)에 도착
- 상하좌우 이동 가능, 생명 최소한으로 잃기
- 죽음 칸은 방문 못하게 하기
- 안전 칸은 비용 0, 위험 칸은 비용이 1이므로 위의 문제들과 유사하다. (덱을 이용하여 0인 경우 먼저 방문, 1인 경우 나중에 방문)
설계
- 일단 500x500 사이즈 보드에 0으로 세팅해두기(기본은 안전)
- 주어진 범위에 따라 위험(1) 표시하기
- 주어진 범위에 따라 죽음(-1) 표시하기 (범위가 겹칠 경우 안전 -> 위험 -> 죽음 순으로 덮어씌워야 하므로)
- 기본 시작점은 (0,0)으로 하고 보드를 벗어나거나 죽음 구역에 방문하는 경우는 건너뛰기
- 최소 비용 업데이트하고 다음 칸이 0인 경우 unshift, 1인 경우 push하기
주의 : 대각선 범위로 값 채울 때 주어지는 값이 항상 왼쪽 위 -> 오른쪽 아래 순서로 주어지지 않으므로 크기 비교해서 범위 잘 정하기!
const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
let idx = 0;
const N = +input[idx++];
const SIZE = 500;
const board = Array.from({length: SIZE+1}, () => Array(SIZE+1).fill(0));
if(N === 0 && +input[1] === 0){
console.log(0);
return;
}
// 위험 구역
while(N > 0 && idx <= N){
const [X1,Y1,X2,Y2] = input[idx++].split(' ').map(Number);
let sx = X1 < X2 ? X1 : X2;
let lx = X1 > X2 ? X1 : X2;
let sy = Y1 < Y2 ? Y1 : Y2;
let ly = Y1 > Y2 ? Y1 : Y2;
for(let j=sx;j<=lx;j++){
for(let k=sy;k<=ly;k++){
board[j][k] = 1;
}
}
}
const M = +input[idx++];
// 죽음 구역
while(M > 0 && idx <= N+M+1){
const [X1,Y1,X2,Y2] = input[idx++].split(' ').map(Number);
let sx = X1 < X2 ? X1 : X2;
let lx = X1 > X2 ? X1 : X2;
let sy = Y1 < Y2 ? Y1 : Y2;
let ly = Y1 > Y2 ? Y1 : Y2;
for(let j=sx;j<=lx;j++){
for(let k=sy;k<=ly;k++){
board[j][k] = -1;
}
}
}
const move = [[0,1], [0,-1], [-1,0], [1,0]];
const dist = Array.from({length: SIZE+1}, () => Array(SIZE+1).fill(Infinity));
const deque = [];
deque.push([0,0]);
dist[0][0] = 0;
while(deque.length){
const [x,y] = deque.shift();
for(let [dx,dy] of move){
const nx = x+dx;
const ny = y+dy;
if(nx < 0 || nx >= SIZE+1 || ny < 0 || ny >= SIZE+1) continue;
if(board[nx][ny] === -1) continue; // 죽음 영역 건너뛰기
const cost = dist[x][y] + board[nx][ny];
if(cost < dist[nx][ny]){
dist[nx][ny] = cost;
if(board[nx][ny] === 0){
deque.unshift([nx,ny])
}else{
deque.push([nx,ny])
}
}
}
}
console.log(dist[SIZE][SIZE] === Infinity ? -1 : dist[SIZE][SIZE]);위처럼 풀었을 때 시간 초과가 떠서 덱을 직접 구현하니 통과했다.
(배열에서 unshift, shift의 시간 복잡도가 O(N)이라 직접 구현하는 것이 빠르다.)
const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
let idx = 0;
const N = +input[idx++];
const SIZE = 500;
const board = Array.from({length: SIZE+1}, () => Array(SIZE+1).fill(0));
class Deque{
constructor(){
this.storage = {};
this.front = 0;
this.rear = 0;
}
size(){
return this.rear - this.front
}
addRear(val){
this.storage[this.rear++] = val;
}
deleteRear(){
if(this.size() === 0) return undefined;
this.rear--
const val = this.storage[this.rear]
delete this.storage[this.rear]
return val;
}
addFront(val){
this.front--
this.storage[this.front] = val
}
deleteFront(){
if(this.size() === 0) return undefined;
const val = this.storage[this.front]
delete this.storage[this.front++]
return val;
}
}
if(N === 0 && +input[1] === 0){
console.log(0);
return;
}
for (let i = 0; i < N; i++) {
const [X1,Y1,X2,Y2] = input[idx++].split(' ').map(Number); // 위험 구역
let sx = X1 < X2 ? X1 : X2;
let lx = X1 > X2 ? X1 : X2;
let sy = Y1 < Y2 ? Y1 : Y2;
let ly = Y1 > Y2 ? Y1 : Y2;
for(let j=sx;j<=lx;j++){
for(let k=sy;k<=ly;k++){
board[j][k] = 1;
}
}
}
const M = +input[idx++];
for (let i = 0; i < M; i++) {
const [X1,Y1,X2,Y2] = input[idx++].split(' ').map(Number); // 죽음 구역
let sx = X1 < X2 ? X1 : X2;
let lx = X1 > X2 ? X1 : X2;
let sy = Y1 < Y2 ? Y1 : Y2;
let ly = Y1 > Y2 ? Y1 : Y2;
for(let j=sx;j<=lx;j++){
for(let k=sy;k<=ly;k++){
board[j][k] = -1;
}
}
}
const move = [[0,1], [0,-1], [-1,0], [1,0]];
const dist = Array.from({length: SIZE+1}, () => Array(SIZE+1).fill(Infinity));
const deque = new Deque();
deque.addRear([0,0]);
dist[0][0] = 0;
while(deque.size() > 0){
const [x,y] = deque.deleteFront();
for(let [dx,dy] of move){
const nx = x+dx;
const ny = y+dy;
if(nx < 0 || nx >= SIZE+1 || ny < 0 || ny >= SIZE+1) continue;
if(board[nx][ny] === -1) continue;
const cost = dist[x][y] + board[nx][ny];
if(cost < dist[nx][ny]){
dist[nx][ny] = cost;
if(board[nx][ny] === 0){
deque.addFront([nx,ny])
}else{
deque.addRear([nx,ny])
}
}
}
}
console.log(dist[SIZE][SIZE] === Infinity ? -1 : dist[SIZE][SIZE]);[백준] 벽 타기
- 난이도 : 골드 3
- 문제 링크 : https://www.acmicpc.net/problem/23563
분석
- 벽 또는 빈칸
- 상하좌우 이동 가능
- 다음 칸이 벽이면 이동 불가능
- 다음 칸이 벽이면 벽에 인접한 칸이다. 이때 벽에 인접한 칸끼리는 시간 소모 없이 이동 가능하다.
- 벽에 인접하지 않으면 이동 시간 + 1
- 시작 지점부터 끝 지점까지 가는 최소 시간 구하기
설계
- 시작 위치, 끝 위치 찾기
- 시작 위치부터 탐색 시작
- 상하좌우 탐색
- 보드 범위 벗어나거나 다음 칸이 벽이면 continue
- 비용 판단 (다음 칸이 벽에 인접한지 판단, 인접하면 0, 인접하지 않으면 1)
- 비용이 적은 쪽으로 먼저 이동.
여기서 한 가지 잘못 판단한 부분이 현재 칸과 상관없이 다음 칸이 벽에 인접한 칸이면 비용없이 이동 가능하다고 생각했는데, 현재 칸도 벽에 인접하고 다음 칸도 벽에 인접해야 비용없이 이동 가능한 것이었다. 이 부분만 신경쓰면 된다!
const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const [H, W] = input.shift().split(' ').map(Number);
const board = input.map(i => i.split(''));
const dist = Array.from({length: H}, () => Array(W).fill(Infinity));
const move = [[0,1], [0,-1], [1,0], [-1,0]]
class Deque{
constructor(){
this.storage = {};
this.front = 0;
this.rear = 0;
}
size(){
return this.rear - this.front
}
addFront(val){
this.front--;
this.storage[this.front] = val;
}
deleteFront(){
const val = this.storage[this.front];
delete this.storage[this.front++];
return val;
}
addRear(val){
this.storage[this.rear++] = val;
}
deleteRear(){
this.rear--;
const val = this.storage[this.rear];
delete this.storage[this.rear];
return val;
}
}
const start = [];
const end = [];
for(let i=0;i<H;i++){
if(start.length === 2 && end.length === 2) break;
for(let j=0;j<W;j++){
if(board[i][j] === "S"){
start[0] = i
start[1] = j
}else if(board[i][j] === "E"){
end[0] = i
end[1] = j
}
}
}
function isAdjacent(x,y){
for(let [dx,dy] of move){
const nx = x+dx;
const ny = y+dy;
if(nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
if(board[nx][ny] === "#") return true;
}
return false;
}
const dq = new Deque();
dq.addRear(start);
dist[start[0]][start[1]] = 0;
while(dq.size() > 0){
const [x,y] = dq.deleteFront();
for(let [dx,dy] of move){
const nx = x+dx;
const ny = y+dy;
if(nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
if(board[nx][ny] === "#") continue;
const nextCost = isAdjacent(x,y) && isAdjacent(nx,ny) ? 0 : 1;
const cost = dist[x][y] + nextCost;
if(cost < dist[nx][ny]){
dist[nx][ny] = cost;
if(nextCost === 0){
dq.addFront([nx,ny])
}else{
dq.addRear([nx,ny])
}
}
}
}
console.log(dist[end[0]][end[1]]);추가로 최적화를 위해 매번 벽에 인접한지를 판단하는 대신 아래처럼 미리 인접 여부를 배열에 저장해두고 쓰면 된다.
const nearWall = Array.from({ length: H }, () => Array(W).fill(false));
for (let i = 0; i < H; i++) {
for (let j = 0; j < W; j++) {
if (board[i][j] === '#') continue;
for (const [dx, dy] of move) {
const ni = i + dx;
const nj = j + dy;
if (ni < 0 || ni >= H || nj < 0 || nj >= W) continue;
if (board[ni][nj] === '#') {
nearWall[i][j] = true;
break;
}
}
}
}
const nextCost = (nearWall[x][y] && nearWall[nx][ny]) ? 0 : 1;[백준] 보물섬
- 난이도 : 골드 5
- 문제 링크 : https://www.acmicpc.net/problem/2589
문제 조건
- L : 육지
- W : 바다
- 육지로만 상하좌우 이동 가능
- 이동하는데 가장 오랜 시간이 걸리는 육지 두 곳에 보물
BFS로 모든 육지에서 이동 가능한 지점까지 걸리는 시간 구하기
이때 걸리는 가장 큰 시간이 정답
const fs = require("fs");
const input = fs
.readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
.toString()
.trim()
.split("\n");
const [N, M] = input[0].split(" ").map(Number);
const MAP = input.slice(1).map((r) => r.split(""));
const move = [
[0, 1],
[0, -1],
[1, 0],
[-1, 0],
];
let answer = -1;
function BFS(i, j) {
const visited = Array.from({ length: N }, () => Array(M).fill(false));
const queue = [];
queue.push([i, j, 0]);
visited[i][j] = true;
while (queue.length) {
const [x, y, d] = queue.shift();
if (answer < d) answer = d;
for (let [dx, dy] of move) {
const nx = x + dx;
const ny = y + dy;
if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
if (visited[nx][ny]) continue;
if (MAP[nx][ny] === "W") continue;
visited[nx][ny] = true;
queue.push([nx, ny, d + 1]);
}
}
}
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
if (MAP[i][j] === "L") {
BFS(i, j);
}
}
}
console.log(answer);[백준] 빙산
- 난이도 : 골드 4
- 문제 링크 : https://www.acmicpc.net/problem/2573
1년에 인접한 0의 개수만큼 높이가 줄어듦. 높이는 0보다 줄어들 수 없음.
빙산이 두 덩어리 이상으로 분리되는 최초의 시간 구하기
다 녹을 때까지 분리되지 않으면 0 출력
0보다 큰 지점(빙산) 상하좌우 인접한 0 개수 구하기 (배열에 저장, x,y,0개수)
한 번에 빙산 높이 줄이기 (0보다 작아지지 않도록 주의)
시간++
BFS로 빙산 개수 구하기 -> 2 이상이면 종료, 미만이면 계속 진행
59%에서 시간 초과 => 매번 맵을 모두 돌면서 빙산 개수와 녹여야 하는 개수를 구하니 시간 초가가 발생했다.
const fs = require("fs");
const input = fs
.readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
.toString()
.trim()
.split("\n");
const [N, M] = input[0].split(" ").map(Number);
const MAP = input.slice(1).map((r) => r.split(" ").map(Number));
const move = [
[0, 1],
[0, -1],
[1, 0],
[-1, 0],
];
let answer = 0;
function BFS(i, j, visited) {
const queue = [];
let idx = 0;
queue.push([i, j]);
visited[i][j] = true;
while (idx < queue.length) {
const [x, y] = queue[idx++];
for (let [dx, dy] of move) {
const nx = x + dx;
const ny = y + dy;
if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
if (MAP[nx][ny] === 0) continue;
if (visited[nx][ny]) continue;
visited[nx][ny] = true;
queue.push([nx, ny]);
}
}
}
while (true) {
// 녹여야 하는 빙산 위치 및 개수 저장
const melt = [];
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
if (MAP[i][j] > 0) {
let zero_cnt = 0;
for (let [dx, dy] of move) {
const nx = i + dx;
const ny = j + dy;
if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
if (MAP[nx][ny] === 0) zero_cnt++;
}
if (zero_cnt > 0) melt.push([i, j, zero_cnt]);
}
}
}
// 빙산 녹이기 (높이가 0보다 작아지지 않도록 설정)
for (let [x, y, c] of melt) {
const height = MAP[x][y] - c;
MAP[x][y] = height < 0 ? 0 : height;
}
// 시간 증가
answer++;
const visited = Array.from({ length: N }, () => Array(M).fill(false));
let cnt = 0;
// 빙산 덩어리 개수 세기
for (let i = 0; i < N && cnt < 2; i++) {
for (let j = 0; j < M && cnt < 2; j++) {
if (MAP[i][j] > 0 && !visited[i][j]) {
BFS(i, j, visited);
cnt++;
}
}
}
// 덩어리가 2개 이상이면 종료
if (cnt > 1) break;
}
console.log(answer);매번 맵을 모두 돌지 않고 초기에 빙산 위치를 구해둔 뒤 이를 바탕으로 다 녹은 빙산은 제거하며 구하면 시간 초과를 해결할 수 있다.
const fs = require("fs");
const input = fs
.readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
.toString()
.trim()
.split("\n");
const [N, M] = input[0].split(" ").map(Number);
const MAP = input.slice(1).map((r) => r.split(" ").map(Number));
const move = [
[0, 1],
[0, -1],
[1, 0],
[-1, 0],
];
let answer = 0;
// 초기 빙산 위치
let iceList = [];
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
if (MAP[i][j] > 0) iceList.push([i, j]);
}
}
function BFS(i, j, visited) {
const queue = [];
let idx = 0;
queue.push([i, j]);
visited[i][j] = true;
while (idx < queue.length) {
const [x, y] = queue[idx++];
for (let [dx, dy] of move) {
const nx = x + dx;
const ny = y + dy;
if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
if (MAP[nx][ny] === 0) continue;
if (visited[nx][ny]) continue;
visited[nx][ny] = true;
queue.push([nx, ny]);
}
}
}
while (true) {
const meltInfo = [];
// 녹는 양 계산
for (const [x, y] of iceList) {
let sea = 0;
for (const [dx, dy] of move) {
const nx = x + dx;
const ny = y + dy;
if (MAP[nx][ny] === 0) sea++;
}
meltInfo.push([x, y, sea]);
}
// 빙산 녹이기 (높이가 0보다 작아지지 않도록 설정)
for (let [x, y, c] of meltInfo) {
const height = MAP[x][y] - c;
MAP[x][y] = height < 0 ? 0 : height;
}
// 시간 증가
answer++;
// 모두 녹은 것 제거
iceList = iceList.filter(([x, y]) => MAP[x][y] > 0);
if (iceList.length === 0) break;
const visited = Array.from({ length: N }, () => Array(M).fill(false));
let cnt = 0;
// 빙산 덩어리 개수 세기
for (const [x, y] of iceList) {
if (!visited[x][y]) {
BFS(x, y, visited);
cnt++;
if (cnt >= 2) {
console.log(answer);
return;
}
}
}
}
console.log(0);[백준] 숨바꼭질 2
- 난이도 : 골드 4
- 문제 링크 : https://www.acmicpc.net/problem/12851
걷기 : -1, +1
순간이동 하기 : *2
가장 빠른 시간과 가장 빠른 방법으로 찾는 방법 가짓수 출력
큰 수 -> 작은 수로 -1, +1, /2를 하며 가짓수를 세려고 했는데 25%에서 틀렸다.
특정 수가 되는 방법의 수가 여러개가 있을 수 있으므로 visited로 방문한 경우를 바로 막아버리면 안 된다.
const fs = require("fs");
const input = fs
.readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
.toString()
.trim()
.split("\n");
const [N, K] = input[0].split(" ").map(Number);
const B = Math.max(N, K);
const S = Math.min(N, K);
const visited = Array(B + 1).fill(false);
let time = Infinity;
let cnt = 0;
const queue = [];
queue.push([B, 0]);
visited[B] = true;
while (queue.length) {
const [l, t] = queue.shift();
if (l === S) {
time = t;
cnt++;
}
if (t > time) break;
if (l % 2 === 0 && !visited[l / 2]) {
visited[l / 2] = true;
queue.push([l / 2, t + 1]);
}
if (l > S && ((l - 1 !== S && !visited[l - 1]) || l - 1 === S)) {
visited[l - 1] = true;
queue.push([l - 1, t + 1]);
}
if ((l + 1 !== S && !visited[l + 1]) || l + 1 === S) {
visited[l + 1] = true;
queue.push([l + 1, t + 1]);
}
}
console.log(time);
console.log(cnt);시간과 방법의 수를 각각 배열로 만들어둔다.
처음 방문한 경우 시간과 방법의 수를 세팅하고 큐에 추가한다.
이미 방문한 경우 방법의 수를 더해준다.
const fs = require("fs");
const input = fs
.readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
.toString()
.trim()
.split("\n");
const [N, K] = input[0].split(" ").map(Number);
const MAX = 100000; // N, K의 최대 범위
const dist = Array(MAX + 1).fill(-1); // 시간
const cnt = Array(MAX + 1).fill(0); // 방법의 수
const queue = [];
let head = 0;
queue.push(N);
dist[N] = 0;
cnt[N] = 1;
while (head < queue.length) {
const cur = queue[head++];
for (const next of [cur - 1, cur + 1, cur * 2]) {
if (next < 0 || next > MAX) continue;
// 처음 방문
if (dist[next] === -1) {
dist[next] = dist[cur] + 1;
cnt[next] = cnt[cur];
queue.push(next);
}
// 같은 최단 거리로 또 도달
else if (dist[next] === dist[cur] + 1) {
cnt[next] += cnt[cur];
}
}
}
console.log(dist[K]);
console.log(cnt[K]);[백준] 치즈
- 난이도 : 골드 3
- 문제 링크 :
- 치즈 좌표 미리 저장
- (0,0)에서 BFS 탐색해서 외부 전부 표시 (치즈가 녹으면서 새로운 외부가 생길 수 있으므로 매번 탐색)
- 치즈 BFS로 탐색해서 두 면 이상이 외부 표면과 닿은 것들 좌표 저장
- 외부 표면과 두 면 이상 닿은 치즈는 전부 0(외부)으로 바꾸기
- 녹은 치즈 제거
- 시간 증가
- 치즈가 모두 녹아 없어지면 시간 반환
const fs = require("fs");
const { join } = require("path");
const input = fs
.readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
.toString()
.trim()
.split("\n");
const [N, M] = input[0].split(" ").map(Number);
const board = input.slice(1).map((r) => r.split(" ").map(Number));
const move = [
[0, 1],
[0, -1],
[1, 0],
[-1, 0],
];
let time = 0;
let cheese = [];
// 치즈 좌표 찾기
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
if (board[i][j] === 1) {
cheese.push([i, j]);
}
}
}
function BFS(i, j, visited) {
const queue = [[i, j]];
visited[i][j] = true;
while (queue.length) {
const [x, y] = queue.shift();
for (let [dx, dy] of move) {
const nx = x + dx;
const ny = y + dy;
if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
if (board[nx][ny] === 1) continue;
if (visited[nx][ny]) continue;
visited[nx][ny] = true;
queue.push([nx, ny]);
}
}
}
while (true) {
const visited = Array.from({ length: N }, () => Array(M).fill(false));
// 치즈 다 녹으면 끝
if (cheese.length === 0) break;
// 외부 표시
BFS(0, 0, visited);
// 외부와 두 면 이상 맞닿은 좌표 저장
const melt = [];
for (let [x, y] of cheese) {
let cnt = 0;
for (let [dx, dy] of move) {
const nx = x + dx;
const ny = y + dy;
if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
if (visited[nx][ny]) cnt++;
}
if (cnt > 1) melt.push([x, y]);
}
// 맞닿은 부분 제거
for (let [x, y] of melt) {
board[x][y] = 0;
}
cheese = cheese.filter(([x, y]) => board[x][y]);
// 시간 증가
time++;
}
console.log(time);최적화 버전
치즈 위치를 저장하지 않고 외부만 탐색할 수 있는 방법도 있다.
외부를 BFS로 돌며 치즈 접촉 카운트를 저장하고 접촉 횟수가 2 이상인 치즈를 없애며 더 이상 녹일 치즈가 없으면 시간을 반환해도 된다.
이렇게 하면 치즈 배열을 매번 새로 갱신하지 않아도 되서 효율적이다.
const fs = require("fs");
const input = fs
.readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
.toString()
.trim()
.split("\n");
const [N, M] = input[0].split(" ").map(Number);
const board = input.slice(1).map(row => row.split(" ").map(Number));
const move = [
[0, 1],
[0, -1],
[1, 0],
[-1, 0],
];
let time = 0;
while (true) {
const visited = Array.from({ length: N }, () => Array(M).fill(false));
const contact = Array.from({ length: N }, () => Array(M).fill(0));
// 외부 공기 BFS
const queue = [[0, 0]];
let head = 0;
visited[0][0] = true;
while (head < queue.length) {
const [x, y] = queue[head++];
for (const [dx, dy] of move) {
const nx = x + dx;
const ny = y + dy;
if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
// 공기면 계속 BFS
if (board[nx][ny] === 0 && !visited[nx][ny]) {
visited[nx][ny] = true;
queue.push([nx, ny]);
}
// 치즈면 접촉 카운트
else if (board[nx][ny] === 1) {
contact[nx][ny]++;
}
}
}
// 녹일 치즈 확인
let melted = false;
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
if (board[i][j] === 1 && contact[i][j] >= 2) {
board[i][j] = 0;
melted = true;
}
}
}
if (!melted) break;
time++;
}
console.log(time);[백준] 불!
-
난이도 : 골드 3
-
문제 조건
#: 벽 - 아무도 통과 못함
.: 지나갈 수 있는 공간
J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
F: 불이 난 공간
지훈은 상하좌우중 하나로 이동
불은 상하좌우로 동시에 확산
가장자리에서 탈출
벽은 통과 못함. -
문제 설계
- 초기 지훈 위치, 불 위치 저장
- 지훈 이동하며 가장자리 도착하면 시간 반환
- 불 확산 - 벽이나 맵 벗어나면 안 됨
- 시간 증가
- 더 이상 지훈 이동 불가능하면 끝
메모리 초과. -> 매번 불 BFS를 반복하며 이미 방문한 곳을 다시 방문하고 지훈 위치도 매번 복사해서 발생.
const fs = require("fs");
const input = fs
.readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
.toString()
.trim()
.split("\n");
const [R, C] = input[0].split(" ").map(Number);
const board = input.slice(1).map((r) => r.split(""));
const visited = Array.from({ length: R }, () => Array(C).fill(false));
const move = [
[0, 1],
[0, -1],
[1, 0],
[-1, 0],
];
let minute = 0;
let J = []; // 지훈 위치
let fire = []; // 불 위치
for (let i = 0; i < R; i++) {
if (J.length > 0 && fire.length > 0) break;
for (let j = 0; j < C; j++) {
if (board[i][j] === "J") {
J = [i, j];
} else if (board[i][j] === "F") {
fire = [i, j];
}
}
}
let queue = [];
queue.push(J);
visited[J[0]][J[1]] = true;
while (true) {
// 탈출 불가능 - 더 이상 이동할 곳 없을 때
if (queue.length === 0) break;
// 지훈 이동 - 상하좌우 중 가능한 방향, 동시에 이동 해야 함!
const cur = [...queue];
queue = [];
while (cur.length) {
const [x, y] = cur.shift();
// 탈출 가능하면 멈추기 - 가장자리
if (x === 0 || x === R - 1 || y === 0 || y === C - 1) {
console.log(minute + 1);
return;
}
for (let [dx, dy] of move) {
const nx = x + dx;
const ny = y + dy;
if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
if (visited[nx][ny]) continue;
if (board[nx][ny] === "#" || board[nx][ny] === "F") continue;
visited[nx][ny] = true;
queue.push([nx, ny]);
}
}
// 불 확산
const fires = [fire];
const fire_visited = Array.from({ length: R }, () => Array(C).fill(false));
fire_visited[fire[0]][fire[1]] = true;
while (fires.length) {
const [fx, fy] = fires.shift();
for (let [dx, dy] of move) {
const nx = fx + dx;
const ny = fy + dy;
if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
if (fire_visited[nx][ny]) continue;
if (board[nx][ny] === "#") continue;
if (board[nx][ny] === "F") fires.push([nx, ny]);
board[nx][ny] = "F";
fire_visited[nx][ny] = true;
}
}
// 시간 증가
minute++;
}
console.log("IMPOSSIBLE");최적화 풀이
불 BFS를 한 번만 돌아도 된다.
먼저 불이 맵의 각 위치에 도달하는 최단 시간을 모두 저장해두고, 지훈이 불보다 빠른 시간에 도달하는 경우 이동하며 가장자리에 도착하면 시간을 반환하면 된다.
불의 확산이 지훈이의 이동과 무관한 독립적인 사건이기 때문에 불 확산을 먼저 따로 처리해도 된다. 이후 조건에 따라 지훈이 이동하면 동시에 이동하는 것과 동일한 결과가 나온다.
const fs = require("fs");
const input = fs
.readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
.toString()
.trim()
.split("\n");
const [R, C] = input[0].split(" ").map(Number);
const board = input.slice(1).map((r) => r.split(""));
const move = [
[0, 1],
[0, -1],
[1, 0],
[-1, 0],
];
const fireTime = Array.from({ length: R }, () => Array(C).fill(Infinity));
const visited = Array.from({ length: R }, () => Array(C).fill(false));
let jq = [];
let fq = [];
// 초기 위치 수집
for (let i = 0; i < R; i++) {
for (let j = 0; j < C; j++) {
if (board[i][j] === "J") {
jq.push([i, j, 0]);
visited[i][j] = true;
}
if (board[i][j] === "F") {
fq.push([i, j, 0]);
fireTime[i][j] = 0;
}
}
}
// 불 BFS
while (fq.length) {
const [x, y, t] = fq.shift();
for (const [dx, dy] of move) {
const nx = x + dx;
const ny = y + dy;
if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
if (board[nx][ny] === "#") continue;
if (fireTime[nx][ny] <= t + 1) continue;
fireTime[nx][ny] = t + 1;
fq.push([nx, ny, t + 1]);
}
}
// 지훈 BFS
while (jq.length) {
const [x, y, t] = jq.shift();
// 가장자리면 탈출
if (x === 0 || x === R - 1 || y === 0 || y === C - 1) {
console.log(t + 1);
return;
}
for (const [dx, dy] of move) {
const nx = x + dx;
const ny = y + dy;
if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
if (visited[nx][ny]) continue;
if (board[nx][ny] === "#") continue;
// 불보다 먼저 도착해야 함
if (t + 1 >= fireTime[nx][ny]) continue;
visited[nx][ny] = true;
jq.push([nx, ny, t + 1]);
}
}
console.log("IMPOSSIBLE");
모든게 새롭고 재밌는 프론트엔드 새싹