본문 바로가기

DFS7

[JS] 코딩테스트 문제 : 섬나라 아일랜드 [DFS] 문제 : 섬나라 아일랜드(DFS 활용) 문제 설명 N*N 의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요. 1 1 0 0 0 1 0 0 1 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 1 1 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 만약 위와 같다면 ▣ 입력설명 첫 번째 줄에 자연수 N(3= 0 && X < board.length) { // 이동할 좌표에이어진 섬이 있는 경우 이동한 위치좌표를 기준으로 추가 탐색을 위해 함수를 재귀적으로 호출 if (board[Y][X] === 1) { console.. 2024. 4. 23.
[JS] 코딩 테스트 문제 : 미로탐색 [DFS] 문제 : 미로탐색(DFS) 문제 설명 7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요. 출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다. 격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면 출발 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 0 0 1 0 0 0 0 0 도착 위의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지이다. ▣ 입력설명 7*7 격자판의 정보가 주어집니다. ▣ 출력설명 첫 번째 줄에 경로의 가지수를 출력한다. ▣ 입력예제 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0.. 2024. 4. 2.
[JS] 코딩 테스트 문제 : 경로 탐색 [인접행렬] 문제 : 경로 탐색(인접행렬) 문제 설명 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 1 2 3 4 5 1 2 5 1 3 4 2 5 1 3 4 5 1 4 2 5 1 4 5 총 6 가지입니다. ▣ 입력설명 첫째 줄에는 정점의 수 N(1 (graph[s][e] = 1)); console.log(graph); // 재귀함수 DFS // current : 현재 노드 번호 1부터 시작하므로 1이 기본값 // chkArr : 현재까지 방문한 노드 순서대로 저장한 배열 시작값은 1 이므로 [1] 이 기본값 function DFS(current = 1, chkArr = [1]) { // n 번.. 2024. 3. 19.
[JS] 코딩 테스트 문제 : 동전교환 [DFS] 문제 : 동전교환 문제 설명 다음과 같이 여러 단위의 동전들이 주어져 있을 때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다. ▣ 입력설명 첫 번째 줄에는 동전의 종류 개수 N(1 2024. 1. 30.
[JS] 코딩 테스트 문제 : 바둑이 승차 [DFS] 문제 : 바둑이 승차(DFS) 문제 설명 철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울수가 없다. 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다. N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요. ▣ 입력설명 첫 번째 줄에 자연수 C(1 2024. 1. 28.
[JS] 코딩 테스트 문제 : 합이 같은 부분집합 [DFS] 문제 : 합이 같은 부분집합(DFS) 문제 설명 N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요. 둘로 나뉘는 두 부분집합은 서로소 집합(Disjoint Set)이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어야 합니다. 예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다. ▣ 입력설명 첫 번째 줄에 자연수 N(1 a + b, 0); let n = arr.length; // 배열의 인덱스를 의미할 파.. 2024. 1. 24.
[JS] 코딩 테스트 문제 : 부분 집합 구하기 [DFS] 문제 : 부분집합 구하기(DFS) 문제 설명 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요. ▣ 입력설명 첫 번째 줄에 자연수 N(1 0); // 현재 원소 L 값이 현재 원소값 L 이 n + 1 이 되는 경우 재귀함수를 종료 function DFS(L) { if (L === n + 1) { let tmp = ""; // ch[L] 값이 1인 경우 그 배열의 인덱스값을 문자열(tmp)에 추가하며 for (let i = 1; i 0) answer.push(tmp.trim()); } // 체크 배열에 L번째(ch[L]) 값이 0인 경우와 1인 경우로 나누어 재귀 함수 호출 else { ch[L] = 1; DFS(L + 1); ch[L] = 0; DFS.. 2024. 1. 23.

티스토리툴바