문제링크https://www.acmicpc.net/problem/11403풀이문제를 풀긴 풀었는데 플로이드 와샬의 점화식을 이용하진 않았다. 해당 점화식을 이용해서 풀면 더 짧은 코드로 작성이 가능하다. 나는 하나의 점을 방문하면서 기존 graph를 갱신하는 방향으로 문제를 풀고 이미 방문한 점은 다시 방문하지 않는 방식으로 계산을 최적화 하였다.let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let [pointsCnt, ...arr] = input;let graph = arr.map((str) => { return str.split(" ").map((n) => Number(n)..

문제링크https://www.acmicpc.net/problem/7569문제풀이이 문제는 3차원 배열(storage)을 만들고 BFS로 그 3차원 배열의 토마토를 순차적으로 익히면 문제를 풀 수 있다. 여기서 f는 floor, r는 row, c는 column의 약자이다. 처음에는 각 위치에 있는 토마토가 익는데 걸리는 시간을 나타내는 3차원배열을 하나 더 만들어 문제를 풀었는데 시간초과가 났었다. 그래서 3차원 하나의 배열을 가지고 문제를 접근하였는데 또 시간초과가 났었다. 고심끝에 while문 내부 if문의 조건을 storage[nextF] && storage[nextF][nextR] && storage[nextF][nextR][nextC] 형태로 3차원배열의 존재여부를 key값들을 이용해 확인하는 형..

문제링크https://www.acmicpc.net/problem/1238문제풀이플로이드 와샬 알고리즘을 이용해서 풀 수 있다. 플로이드 와샬 시간복잡도가 O(n^3) 이기 때문에 시간초과의 염려이 있었지만 다행히 통과!// https://www.acmicpc.net/problem/1238let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let [N, M, X] = input .shift() .split(" ") .map((n) => Number(n));let graph = Array.from({ length: N }, () => { return Array(N).fi..

문제https://www.acmicpc.net/problem/2667 풀이일단 지도를 2차원배열 형태로 변환시켰고 이를 이용해서 단지별로 아파트를 묶었다. dfs를 이용해서 특정 아파트에서 갈수 있는 모든 아파트를 하나의 단지로 묶었고 그 과정에서 단지내의 아파트의 갯수를 확인했다.그렇게 apartment 라는 array에 단지내의 아파트 갯수를 push 한뒤 다시 아파트갯수를 오름차순으로 정렬하여 문제의 답을 구할 수 있었다.let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let N = Number(input.shift());// 지도 2차원 배열로 저장let map = [];// ..

문제https://www.acmicpc.net/problem/1916 풀이처음에 dfs로 접근해서 풀었는데 시간초과로 틀려서 dp를 이용했다. 일단 map이라는 2차원 배열을 구현한다. 이 2차원 배열의 map[ i ][ j ] 는 i도시에서 j 도시로 갈 시 가장 가격이 싼 버스 요금을 나타 낸다. 만약 map[ i ][ j ] = Infinity 이면 해당 루트는 버스가 다니지 않는다고 생각하면 된다.  그리고 dp라는 2차원 배열을 구현한다. dp[ i ][ j ] 는 i 도시에서 j 도시로 가는 루트는 가장 버스요금이 싼 루트의 요금을 나타낸다.우리는 모든 경로를 탐색하면서 2차원 배열 dp를 완성시키고 최종적으로 dp[출발점][도착점] => 최소비용 을 구하면 된다.  const fs = req..