백준/너비 우선 탐색
-
백준 2573 nodejs백준/너비 우선 탐색 2023. 3. 1. 14:19
문제 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 1년 단위로 BFS를 실행해 빙산을 녹인다. 1년이 새로 시작될 때마다 DFS를 실행해 빙산이 전부 연결돼 있는지 확인한다. let [[N, M], ...I] = `${require('fs').readFileSync(0)}`.trim().split`\n`.map(e => e.split` `.map(Number)) class Node { constructor(e) { this.val..
-
백준 4991 nodejs백준/너비 우선 탐색 2023. 1. 16. 17:28
문제 https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 풀이 더러운 칸과 시작 위치를 정점으로 하는 그래프를 만든다. BFS로 각 정점 사이의 거리를 구한다. DFS와 백트래킹을 이용해 최단 경로를 구한다. let I = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n') I.pop() let [i, O] = [0, []] while (i < I.length) { const [w,..
-
백준 2206 nodejs백준/너비 우선 탐색 2022. 12. 28. 17:30
문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 BFS를 이용해 최단 거리를 구한다. visited 배열이 2개(벽을 부수기 전, 벽을 부순 후) 필요하다. Class 사용 let [X, ...I] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n') const [[N, M], D] = [X.split(' ').map(Number),..
-
백준 16236 nodejs백준/너비 우선 탐색 2022. 12. 13. 11:50
문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 BFS를 이용해 먹을 수 있는 물고기와의 거리를 구한다. 해당하는 거리의 좌측 상단 물고기를 찾아서 잡아먹고 Queue를 초기화한다. let [N, ...I] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n') N = +N I = I.map(e => e.split(' ').map(Number)) let..
-
백준 9019 nodejs백준/너비 우선 탐색 2022. 12. 10. 18:04
문제 https://www.acmicpc.net/problem/9019 풀이 BFS를 이용해 A에서 B로 이동하는 최단 경로를 구한다. Array let [T, ...I] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n') const O = [] I.forEach(e => { const [A, B] = e.split(' ').map(Number) const [V, Q] = [Array(10000).fill(0), [[A, '']]] V[A] = 1 let i = 0 while (i < Q.length) { const [curr, comm] = Q[i++] if (curr == B) { O.push(comm) break } co..