문제 https://www.acmicpc.net/problem/1325 row.split(" ").map(Number)); let graph = Array.from({ length: n + 1 }, () => []); let hacked = Array.from({ length: n + 1 }, () => 0); for (let [s, e] of pairs) { graph[e].push(s); } // 각 노드에서 해킹할 수 있는 컴퓨터 수 세기 for (let i = 1; i 0); const q = new Queue(); let cnt = 1; let max = Number.MIN_SAFE_INTEGER; ch[i] = 1; q.push(i); while (!q.isEmpty()) { const v =..
문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 입력 const fs = require("fs"); const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; const [N, ...arr] = fs.readFileSync(filePath).toString().trim().split("\n"); const [n, m] = N.split(" ").map(Number); let board ..
문제 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 그래프를 입력 받아 인접 리스트를 만들고, 해당 리스트를 DFS와 BFS로 순회하면서 [부모, 자식]을 배열에 저장한다. 자식을 기준으로 sort한 다음 부모만 map으로 추출하여 answer를 구한다. for문에서 배열을 순회하며 console.log()를 했더니 시간 초과가 났다. 백준에서는 conosole로 답을 출력할 때 한 번에 모아서 처리해야 한다는 점에 유의해야겠다. 또 #1, #2처럼 배열에 따로 [부모, 자식]을 저장해서 sort하는..
문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 const fs = require("fs"); const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; let [nums, ...arr] = fs.readFileSync(filePath).toString().trim().split("\n"); const [n, m, v..
문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이 const fs = require("fs"); const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; const [total, pairCount, ...pairs] = require("fs") .readFileSync(filePath) .toString() .trim() .split("\n"); const t..
문제 N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌 우와 대각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요. 풀이 #1 DFS function solution(arr) { const n = arr.length; const dx = [-1, -1, 0, 1, 1, 1, 0, -1]; const dy = [0, 1, 1, 1, 0, -1, -1, -1]; let answer = 0; function DFS(x, y) { for (let i = 0; i = 0 && nx < n && ny..
문제 현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요. 풀이 BFS는 큐를 이용한다. BFS는 각 레벨을 모두 살펴보고 다음 레벨로 내려가는 레벨 탐색을 사용하기 때문에 출발점에서 도착지로 가는 최단 거리를 구할 때 사용한다. ⭐⭐⭐ 레벨 탐색을 하게 되면 한 번만에 갈 수 있는 레벨의 정점을 모두 탐색한 후에 두 번만에..
문제 7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요. 출발점은 격 자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다. 격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면 위의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지이다. 풀이 function solution(arr) { const n = arr.length; const dx = [-1, 0, 1, 0]; const dy = [0, 1, 0, -1]; let answer = 0; function DFS(x, y) { if (x === n - 1 && y === n - 1) { answer += 1; } else { for (let i = 0;..
