숨바꼭질
너비 우선 탐색, 최단거리 문제
문제 해결 아이디어
모든 순간이동 (간선)의 비용이 1초 이므로 BFS로 최단 시간을 계산할 수 있음
각 초마다 이동해서 나올 수 있는 모든 조합들에 대해 찾고 거기서 가장 짧은 거리를 찾으면 됨
풀이
function solution()
{
let n = 5; // 언니 위치
let k = 17; // 동생 위치
let max = 10000
let visited = new Array(max).fill(0)
// 답 4 --------
let queue = [];
function bfs() {
queue.push(n) // 큐에 맨 처음에 n 넣기
while (queue.length) {
let cur = queue.shift() // 앞에서 부터 한 개 씩 뺌
if (cur == k) { // 동생의 위치라면 그 위치 리턴
return visited[cur]
}
for (let next of [cur-1, cur+1, cur*2]) { // 4, 6, 10
if (next < 0 || next >= max) continue; // 시공간 넘어갈 경우 무시
if (visited[next] == 0) {
visited[next] = visited[cur]+1; // 6번째를 +1한 값이 visited[4]
queue.push(next) // 4 6 10 // 다음 후보로 넣어주기
}
}
}
}
console.log(bfs())
}이분 그래프
그래프 문제가 나왔을 땐 종이에 그려보면서 푸는 것이 좋음
각 노드가 이동할 때마다 색이 바뀌느냐를 확인
2가지 함수를 사용 bfs와 isBipartite (인접한 인덱스들로 이분 그래프인지 확인)
풀이
function solution()
{
let v = 4
let e = 4
let arr = [[1, 2], [2, 3], [3, 4], [4, 2]]; // NO
// let v = 3
// let e = 2
// let arr = [[1, 3], [2, 3]]; // YES
let graph = [];
// 서로 연결됨을 확인
for (let i=1; i<=v; i++) graph[i] = [];
for (let i=1; i<=e; i++) {
let a = arr[i-1][0]
let b = arr[i-1][1]
graph[a].push([b])
graph[b].push([a])
}
let visited = new Array(v+1).fill(-1)
for (let i=1; i<=v; i++) {
if (visited[i] == -1) { // 아직 방문하지 않았다면 모드 노드들을 다 검사
bfs(i, graph, visited) / bfs를 이용해 색칠
}
}
if (isBipartite(graph, visited)) console.log("YES")
else console.log("NO")
}
// 1번 bfs 함수로 색칠하기 | 0 : 빨강, 1 : 파랑
function bfs(x, graph, visitied) {
queue = [];
queue.push(x) // 큐에 시작 노드를 삽입
visitied[x] = 0; // 빨강으로 시작
while (queue.length) {
x = queue.shift(); // 한 개씩 빼서 조사
for (let y of graph[x]) { // 뺀 애의 인접 노드들 조사
if (visitied[y] == -1) { // 아직 색칠 안 했다면 파랑으로
visitied[y] = (visitied[x] + 1) % 2;
queue.push(y) // 칠하고 넣어주기 (다음 인접 조사를 위해)
}
}
}
}
// 2번 확인 함수
function isBipartite(graph, visited) {
for (let x=1; x<visited.length; x++) { // 처음부터 모든 노드까지 다 조사 했을 때
for (let y of graph[x]) {
// 인접한 노드가 같은 색이라면 이분 그래프 X
if (visited[x] == visited[y]) return false
}
}
return true
}4연산
BFS문제는 최단 거리를 찾거나 최소 횟수를 찾는 문제에서 많이 사용 된다.
주어진 연산에 따라 정수 s에서 탐색을 시작하는 것이므로 BFS를 수행.
이처럼 같을 경우도 존재
풀이
function solution() {
let s = 7;
let t = 256;
let queue = [];
queue.push([s, ''])
let visited = new Set([s]) // set을 통해 중복 검열
let found = false;
if (s == t) { // 두 값이 같다면 0을 return
console.log(0)
}
while (queue.length) {
let [value, opers] = queue.shift(); // 한 개 꺼내고 검사
// 반복이 될수록 value값엔 연산이 된 값이 들어가므로 답일시 바로 return
if (value > 1e9) continue // 값이 10억을 넘어가 못찾고 있으면 그냥 끝내기
if (value == t) {
console.log(opers)
found = true // 답을 찾았으면 found의 값을 true로
break;
}
for (let oper of ['*', '+', '-', '/']) {
let nextValue = value; // 해당하는 값을 넣어줘서 자신만의 연산
if (oper == '*') nextValue *= value
if (oper == '+') nextValue += value
if (oper == '-') nextValue -= value
if (oper == '/' && value != 0) nextValue = 1
if (!visited.has(nextValue)) {
queue.push([nextValue, opers + oper]) // 답이 아니었다면 연산 지속
visited.add(nextValue) // 해당 값도 넣어줌
}
}
}
if (!found) console.log(-1) // 아무리 돌려도 답이 없을 땐 -1
}경쟁적 전염 ★
문제 해결 아이디어
모든 간선의 비용 1, 너비우선 탐색을 이용하여 최단 거리 계산 가능
초기 큐에 원소를 삽입할 때 낮은 바이러스의 번호부터 삽입하여 낮은애부터 번식하도록 함
풀이
function solution()
{
let n = 3; // 가로, 세로 길이
let k = 3; // 1번부터 k번까지의 바이러스 수
let graph = [ [1, 0, 2], [0, 0, 0], [3, 0, 0]]
let target = [2, 3, 2]
// 답 : 3 -------------
let data = []; // 바이러스의 정보를 담을 배열
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
if (graph[i][j] !== 0) {
// 처음 시작 할 때에 존재하는 바이러스에 대한 모든 정보들
// 바이러스 값, 초, x좌표, y좌표
data.push([graph[i][j], 0, i, j])
}
}
}
// 바이러스의 값이 낮을 순으로 큐에 넣어줌
data.sort( (a,b) => a[0] - b[0])
let queue = [];
for (let v of data) {
queue.push(v)
}
// 찾은 시간, 좌표값들
let [targetS, targetX, targetY] = target
console.log(queue)
// 바이러스가 퍼져나가는 위치
let dx = [-1, 0, 1, 0]; // 왼쪽오른쪽
let dy = [0, 1, 0, -1]; // 위아래
while (queue.length) {
// 바이러스가 값이 낮은 애부터 빼줌
let [바이러스, 시간, x, y] = queue.shift()
if (시간 == targetS) break // 시간이 targetS초 지나거나, 큐가 비었을 때 멈춤
for (let i=0; i < 4; i++) { // 4가지 방향에 대한 위치
let nx = x + dx[i]; // x는 -1, 1 (좌, 우)
let ny = y + dy[i]; // y는 1, -1 (상, 하)
if (0 < nx && nx < n && 0 < ny && ny < n) { // 주어진 칸에서
if (graph[nx][ny] == 0) { // 해당곳에 바이러스가 없다면
graph[nx][ny] = 바이러스; // 상하좌우에 바이러스 값을 삽입
queue.push([바이러스, 시간, x, y]) // 한 턴 다음을 위한 바이러스를 queue에 삽입
}
}
}
}
console.log(graph[targetX-1][targetY-1]) // x번째 y번째에 값이니까 인덱스라서 -1씩
}
특정 거리의 도시 찾기 ★
모든 간선의 길이 1
특정한 도시 X를 시작점으로 BFS를 수행하여 모든 도시까지의 최단거리를 계산
각 노드의 최단거리를 하나씩 확인하여 값이 K인 경우에만 해당도시의 번호를 출력★ 팁! ★
단방향 일 땐
한 방향으로만 넣어주면 됨.
풀이
function solution()
{
let n = 4; // 도시의 개수
let m = 4; // 도로의 개수
let k = 2; // 찾을 거리
let x = 1; // 출발할 도시
let tree = [[1, 2], [1, 3], [2, 3], [2, 4]];
// let n = 4; // 도시의 개수
// let m = 4; // 도로의 개수
// let k = 1; // 찾을 거리
// let x = 1; // 출발할 도시
// let tree = [[1, 2], [1, 3], [2, 3], [2, 4]];
// let n = 4; // 도시의 개수
// let m = 3; // 도로의 개수
// let k = 2; // 찾을 거리
// let x = 1; // 출발할 도시
// let tree = [[1, 2], [1, 3], [1, 4]];
let graph = [];
for (i=1; i<=tree.length; i++) graph[i] = []
for (i=0; i<tree.length; i++) {
let a = tree[i][0]
let b = tree[i][1]
graph[a].push(b)
}
let distance = new Array(n+1).fill(-1)
distance[x] = 0 // 출발할 도시에서 거리는 0
let queue = [];
queue.push(x) // 시작값 (시작할 도시)을 큐에 넣고
// console.log(graph)
// bfs 수행
while(queue.length) {
let cur = queue.shift() // 시작값부터 시작
// graph[cur]의 갯수가 두 개면 for문 두 번 반복
for (let next of graph[cur]) { // 그래프의 1번에서 출발
if(distance[next] === -1) { // 아직 방문 안 했다면
distance[next] = distance[cur] + 1 // 0에다가 1더한 값이 다음 목적지까지의 거리
// 위 코드 : 그래프의 1번 (출발점)이 0이었으니 0+1 -> 즉, 1을 2까지의 거리로 지정
queue.push(next) // 1번에서 2번으로 갔으니 2를 큐에 넣어주고, 그 다음 3을 넣어줌
}
}
}
// console.log("최종", queue)
// console.log(distance)
let flag = false;
let ans = [];
for (i=1; i<distance.length; i++) {
if (distance[i] === k) {
ans.push(i)
flag = true
}
}
!flag ? console.log(-1) : console.log(ans)
}설명
노드의 값들이 주어졌으므로 연결해주기 위해 서로를 연결하는데 여기선 단방향으로 움직이기 때문에 a와 b만을 연결해준다.
그 후 거리값들을 모두 -1로 해준 뒤 출발하는 곳의 값만 0으로 바꾼 후
while문을 돌며 출발에서 갈 수 있는 곳들의 거리를 distance[x] (0) 에서 +1를 해주어 거리를 1씩 늘려간다
환승 ★★
문제 해결 아이디어
하이퍼튜브 하나는 역 K개를 서로 연결함, 방문하는 최소 역의 수를 출력하면 되는데, BFS로 최단거리를 계산하되, 역의 수를 구하는 것이므로 계산된 최단 거리를 2로 나누면 된다.
만약 간선의 비용이 서로 다르다면 다익스트라와 같은 방법을 사용해야함
하이퍼튜브를 노드로 간주하고 BFS를 수행
각 하이퍼튜브와 하이퍼튜브가 연결하는 노드들을 모두 양방향 간선으로 연결
단 여기서 중요한 것은 최단 거리를 2로 나누고 1을 더한 값이 답
하이퍼노드도 역으로 생각했으니까 그만큼을 나누고 빼준 후 시작하는 1도 역이니까 1도 포함
풀이
function solution()
{
let n = 9; // 역의수
let k = 3; // 하이퍼튜브가 연결하는 역의 수
let m = 5; // 하이퍼튜브 수
// 1번역에서 n번역까지 가는데 방문하는 역의 최소 갯수
let tree = [[1, 2, 3], [1, 4, 5], [3, 6, 7], [5, 6, 7], [6, 8, 9]]
// let n = 15;
// let k = 8;
// let m = 4;
// // 1번역에서 n번역까지 가는데 방문하는 역의 최소 갯수
// let tree = [[11, 12, 8], [14, 13, 6], [10, 7, 1], [5, 8, 12], [13, 6, 2], [4, 10, 15],[4, 5, 9],[9, 8, 14], [12, 11, 12], [14, 3, 5], [6, 1, 13]]
let graph = [];
// m개의 노드도
for (let i=1; i<= n+m ; i++) graph[i] = [] // 9개의 역 + 하이퍼튜브 수
for (let i = 1; i<=m; i++) {
for (let x of tree[i-1]) {
graph[x].push(n+i); // 노드 -> 하이퍼 튜브
graph[n+i].push(x) // 하이퍼 튜브 -> 노드
}
}
console.log(graph)
let visited = new Set([1]) // 1번에서 출발
let queue = [];
queue.push([1, 1])
let found = false;
while (queue.length) {
let [dist, now] = queue.shift()
if (now == n) {
// 절반은 하이퍼 튜브니까 나눠서 빼주기
console.log(parseInt( dist / 2 ) +1)
found = true
break;
}
for (let y of graph[now]) { // 인접노드
if(!visited.has(y)) {
queue.push([dist+1, y])
visited.add(y)
}// 아직 방문 안 했다면
}
}
if (!found) console.log(-1)
}결혼식
BFS의 가장 기본적인 문제
풀이
문제 해결 아이디어
친구, 친구의 친구라는 거는 거리가 2이하라는 것
function solution()
{
let n = 6;
let m = 5;
let tree = [[1, 2], [1, 3], [3, 4], [2, 3], [4, 5]]
// let tree = [[2, 3], [3, 4], [4, 5], [5, 6], [2, 5]]
// 답 3 ------------
let graph = [];
for (let i=1; i<= n; i++) graph[i] = []
for (let i=0; i<tree.length; i++) {
let a = tree[i][0]
let b = tree[i][1]
graph[a].push(b)
graph[b].push(a)
}
console.log(graph)
let distance = new Array(m+1).fill(-1)
distance[1] = 0
let queue = [];
queue.push(1)
while(queue.length) {
let cur = queue.shift()
for (let next of graph[cur]) {
if(distance[next] === -1) {
distance[next] = distance[cur]+1
queue.push(next)
}
}
}
console.log(distance)
console.log(distance.filter( v => v === 1 || v === 2).length)
}치즈
https://www.acmicpc.net/problem/2638
문제 풀이 핵심 아이디어
치즈의 생김새를 보고 계산해서 지워가는 것이 아닌, 항상 가장자리에는 치즈가 없으므로 거기서부터 출발하여 1이 되는 곳은 지워주면 됨
(0, 0)의 위치에서 출발하여 BFS 를 진행
-> 큐에서 하나의 우너소를 꺼낸 뒤, 상, 하 ,좌, 우 위치를 확인
인접한 치즈가 있다면, 치즈가 있는 위치에 대해 카운트녹이기 파트
-> 카운트가 2 이상인 치즈를 없앤다. (2개 이상의 공기에 노출되어 있는 애들)
풀이
function solution()
{
let n = 8;
let m = 9;
let graph = [
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 0, 1, 1, 0],
[0, 0, 1, 1, 1, 1, 1, 1, 0],
[0, 0, 1, 1, 1, 1, 1, 0, 0],
[0, 0, 1, 1, 0, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0]
];
let dx = [-1, 0, 1, 0]
let dy = [0, 1, 0, -1]
function bfs() {
let visited = []
for (i=0; i<graph.length; i++) visited.push(new Array(m).fill(false))
visited[0][0] = true
let queue = [];
queue.push([0, 0])
while(queue.length) {
let [x, y] = queue.shift()
for (let i=0; i<4; i++) {
let nx = x + dx[i];
let ny = y + dy[i];
// 맵을 벗어나면 무시 (필수)
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue
if (!visited[nx][ny]) { // false인 곳들 (아직 방문 안 한 곳)에서
if (graph[nx][ny] >= 1) { // 치즈가 있다면
graph[nx][ny] += 1 // 카운트를 증가시킴
} else {
queue.push([nx, ny]); // 치즈가 없다면 - 다음 상, 하, 좌, 우 차례들 넣어주기
// 여기서 유의해야할 것은 1은 치즈가 있다는 것이고, 값을 1씩 늘리는 것이 한 변
// 즉 3이상이 돼야 녹을 치즈라는 것
visited[nx][ny] = true // 방금 방문 했던 곳을 true로
}
}
}
}
}
function melt() {
let finish = true;
for (let i=0; i< n; i++) {
for (let j=0; j<m; j++) {
if (graph[i][j] >= 3) {
graph[i][j] = 0;
finish = false
}
// 값이 2라는 건 한 면만 닿아있는 거라 그냥 무시하려고 1 삽입
else if ( graph[i][j] == 2 ) graph[i][j] = 1
}
}
return finish // 더 녹일 치즈가 없다면 finish를 리턴
}
let result = 0;
while (true) {
bfs(); // 치즈 바깥라인 한번 녹이기 (즉, 1시간 흐름)
if (melt()) { // 더 녹일 치즈가 없으면 result 반환
console.log(result)
break;
}
else result +=1; // 한 사이클이 돌릴 때마다 +1
}
}A->B (bfs 버전) ★★
풀이
function solution()
{
let n = 2;
let m = 162;
let queue = [];
queue.push([n, 0]) // 시작값, 연산횟수
let visited = new Set() // set으로 만들어 중복제거
let found = false; // 같으면 멈추기
if ( n == m ) console.log(0)
while(queue.length) {
let [value, dist] = queue.shift()
if (value > 1e9) continue // 값이 10억을 넘어갔으면 건너뛰기
if ( value === m ) {
console.log(dist+1) // 찾았으면 여태 연산 +1
found = true
break
}
for (let oper of ['*', '+']) { // 두 가지 선택 배열 생성
let nextValue = value;
if (oper === '*') { // nextValue 생성 후 값을 전달
nextValue *= 2
}
if (oper === '+') {
nextValue *= 10;
nextValue += 1;
}
if (!visited.has(nextValue)) {
queue.push([nextValue, dist+1]) // 두 값모두 연산횟수와 함께 넣어줌
visited.add(nextValue) // *, + 두 값 모두 넣어줌
}
}
}
}
기록, 꺼내 쓸 수 있는 즐거움