문제 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..
문제 현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 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;..
문제 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프 로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 총 6 가지입니다. 풀이 function solution(n, arr) { let ch = Array.from({ length: n + 1 }, () => 0); let graph = Array.from({ length: n + 1 }, () => []); let answer = 0; for (let [a, b] of arr) { graph[a] = [...graph[a], b]; } console.log(graph); function DFS(v) { if (v === n) answer += 1; else { for (let i..
문제 N개의 정수가 주어지면 그 숫자들 중 K개를 뽑는 조합의 합이 임의의 정수 M의 배수인 개수는 몇 개가 있는지 출력하는 프로그램을 작성하세요. 예를 들면 5개의 숫자 2 4 5 8 12가 주어지고, 3개를 뽑은 조합의 합이 6의 배수인 조합을찾으면 4+8+12 2+4+12로 2가지가 있습니다. 풀이 function solution(n, k, arr, m) { let answer = 0; function DFS(L, s, sum) { if (L === k && sum % m === 0) answer += 1; else { for (let i = s; i < n; i++) { DFS(L + 1, i + 1, sum + arr[i]); } } } DFS(0, 0, 0); return answer; } 1..
문제 1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성하세요. 풀이 조합의 경우는 간단하게 아래로 가지를 뻗을 때 현재 숫자 뒤부터 확인한다고 생각하면 된다. 조합에서는 현재까지 포함한 숫자를 다음 경우를 생각할 때 모두 제외하는 것이 중요하기 때문에 DFS 함수는 각 레벨을 나타내는 L과 각 L 자리에 들어갈 요소를 모두 확인하는 for문의 시작점인 start를 매개변수로 넘겨준다. 즉, for문을 돌 때 초기값인 start를 넘겨주어 이전에 사용한 값을 다시 사용하지 않도록 한다. function solution(n, r) { let c = Array.from({ length: r }); let answer = []; function DFS(L, s..
문제 가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼 의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이그려진다. 3 1 2 4 4 3 6 7 9 16 N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오. 단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다. 풀이 #1 function countCombs(n, r) { let memo = Array.from({ length: n + 1 }, () => Array.from({ length: r + 1 }, () => 0) ); funct..
