문제https://www.acmicpc.net/problem/1753 풀이이번 문제는 다익스트라 알고리즘 문제이다. 필자는 BFS를 이용한 다익스트라 알고리즘 구현을 시도했지만, 시간 초과 에러가 발생했다.이유는 BFS의 탐색 방식에 있다. 필자의 BFS는 큐에 탐색할 경로의 정보를 담고 하나씩 가져오며 완전 탐색을 진행했다. 불필요한 경로까지 검증하면 시간 복잡도가 높아진다.... 이를 해결하기 위해서는 항상 최소의 값을 가져올 수 있는 최소힙을 이용해야 한다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim..
BFS
문제https://www.acmicpc.net/problem/2606 풀이해당 문제는 DFS와 BFS 풀이 모두 가능한 문제이다. 간단한 문제이기 때문에 DFS와 BFS를 다시 연습하기 위해 풀이했다. BFS 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n');const n = +input.shift();const linked = +input.shift();const arr = input.map(e => e.split(' ').map(Number));const map = {};const ..
문제https://www.acmicpc.net/problem/5972 풀이다익스트라다와 BFS 알고리즘을 이용한 문제이며, 필자는 큐를 이용한 풀이를 진행했다. 1번부터 시작하며 큐에 시작하는 위치를 저장하고 순회를 시작한다. 순회하며 각 지점에 도달하기 까지의 최소 비용을 측정한다. 최단 거리의 경우 st 지점부터 ed 지점까지 소요되는 비용을 더하며 최소 비용을 구한다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n').map(e => e);const [n, m] = input.shi..
문제https://school.programmers.co.kr/learn/courses/30/lessons/250136 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이그냥 일반적인 BFS 문제로 처음 파악을 했다. 근데 풀어보니 틀리기도 했고 효율성 검사도 통과하지 않았다.const bfs = (arr, x) => { const start = Array.from({length: arr.length}, (_, i) => [i, x]); for(let i = 0; i = 0 && ny >= 0 && nx 1) continue; ..
문제https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이이번 문제는 최소 비용을로 각 노드를 연결해야 하는 문제이다. BFS 알고리즘을 이용해 인접한 노드를 방문하고 끝 지점까지 연결해야 하며 각 노드까지 연결되는데에 필요한 비용을 DP알고리즘을 이용해 저장한다.(시간 복잡도와 노드와 노드를 연결할 시 비용을 계산) 하지만, 이 문제에서는 한가지 트릭을 추가적으로 생각해야한다. 바로 한 노드로 들어오는 방향까지 생각해야한다. 이유는 커브길을 만들 ..
문제https://www.acmicpc.net/problem/1926 풀이이 문제는 BFS 알고리즘을 이용해 그래프 탐색을 진행해야 한다. 그림은 연결되어 있기 때문에 연결된 노드를 탐색하며 방문했음을 기록해야합니다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n').map(e => e.split(' ').map(Number));const [y, x] = input.shift();const map = input;const check = Array.from({ length: y }, () ..
