BFS

[프로그래머스 / Javascript] 전력망을 둘로 나누기

문제 https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 해당 문제는 송전탑의 연결 상태를 파악한 후 모든 전선을 한번씩 잘라보며 각 전원의 송전탑의 수의 차이를 구하는 문제이다. 문제를 풀 때 송전탑의 연결을 송전탑의 오브젝트에 넣어두어 연결 상태를 확보한 후 끊긴 이 후 송전탑의 수를 구했다. 글보다 코드를 보면 이해가 쉬울 것 같다. function countLink (link,start) { let answer = 0; const..

[백준] 1261번 알고스팟_Node.js

문제 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제 풀이 해당 문제는 BFS문제이다. 하지만 도달하는 최단 거리가 아닌 벽을 최소한으로 부수는 경우를 찾는 것이다. 그렇기에 탐색에 있어서 우선순위가 존재한다. 벽을 최대한 부수지 않는 방식으로 진행하되 목적지에 도달 할 수 없을 때 최소의 벽을 부순다. 이를 구현하기 위해서는 BFS에서 사용되는 queue에 우선순위 별로 넣으면 된다. 기존의 문제에서 queue를 사..

[백준] 14226번 이모티콘 - Node.js

문제 문제 풀이 해당 문제는 3가지 진행 방식으로 진행하여 원하는 개수의 이모티콘을 만드는 최소의 방법을 구하는 문제이다. 최소의 방법을 구하기 위해 BFS를 사용하였다. 3가지의 진행 방식을 아래와 같이 오브젝트로 생성하였다. count는 현재 이모티콘의 길이, x는 클립보드의 저장된 이모티콘의 길이이다. const actionCase = { copy (count ,x){ return [count ,count] }, paste (count ,x){ return [count + x, x] }, deleteOne (count,x){ return [count-1,x] } } 해당 진행 방식으로 BFS로 진행하면 된다. 하지만 일반적인 BFS문제와 다른 점이 있다. 그것은 클립보드이다. 일반적인 BFS문제는 ..

[백준] 1697번 숨바꼭질 _ Node.js

문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 풀이 이 문제는 1초씩 움직이며 동생에게 도착하는 최소 시간을 구하는 문제이므로 BFS를 사용해보았다. 수빈이는 1초마다 +1 , -1 , X2로 세가지 방법으로 움직일 수 있다. 이 때 위치는 0 stdin[line++]; })(); function solution(){ const [N, K] = input().split(" ").map(Number); co..

BFS/DFS(Breadth/Depth First Search)

BFS와 DFS는 그래프를 그려 그래프 안을 돌아다니며 알맞는 경우를 찾을 때 사용되는 알고리즘이다. 이 알고리즘들은 하나의 저장장소와 visited 저장 장소를 이용하여 그래프의 규칙을 찾게 된다. BFS BFS는 Breadth Frist Search의 약자로 말 그대로 너비 우선 탐색을 하는 알고리즘이다. BFS는 Queue를 사용하여 경우의 수를 저장한다. 해당 queue에서 shift를 이용하여 얕은 깊이의 요소들을 우선적으로 계산을 진행한다. 이를 통하여 시작 지점에서 너비 우선적으로 반환하는 프로그램을 작성할 수 있다. 아래 그림을 보자 A지점에서 BFS 방식으로 Graph Traversals을 해보자 BFS는 queue에 저장을 하며 경우가 완료 되면 pop을 해주고, 방문하거나 접촉한 배열..