반응형

1.  문제

■ DFS를 이용하여 리스트의 조합(combination)을 구현한다.

 

2. 핵심요약

■ DFS 알고리즘 활용법을 알아보자.

 

3. JavaScript 코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
let arr = [1, 2, 3, 4, 5];   // 주어진 배열
let result = [];              // 결과를 저장할 배열
let combination = [];         // 현재 조합을 저장할 배열
 
// 깊이 우선 탐색(DFS)을 수행하는 함수
const dfs = (startIndex) => {
    // 종료 조건: 선택된 원소의 개수가 k개가 되면 조합을 결과에 추가
    if (combination.length === 3) { // 예시로 3개 원소를 고르는 조합을 찾는 경우
        result.push([...combination]); // 조합을 결과에 추가
        return;
    }
 
    // startIndex부터 배열의 끝까지 순차적으로 탐색
    for (let i = startIndex; i < arr.length; i++) {
        combination.push(arr[i]);    // 원소를 현재 조합에 추가
        dfs(i + 1);                  // 다음 원소로 이동 (중복을 피하기 위해 i+1로 호출)
        combination.pop();           // 백트래킹: 원소를 제거하고 다른 경우를 시도
    }
}
 
// DFS 탐색 시작
dfs(0);
 
// 결과 출력
console.log(result);
 
 cs

 

4. 참고

https://languagestory.tistory.com/380

 

[DFS] 개념(Depth First Search; 깊이 우선 탐색) - 자바스크립트

1. DFS(Depth First Search; 깊이 우선 탐색)의 개념■ 그래프에서 모든 노드를 한번씩 탐색하기 위한 방법■ 스택 또는 재귀함수를 이용하여 구현■ 루트 노드[또는 임의의 노드]에서 시작하여 형제(si

languagestory.tistory.com

 

반응형
저작자표시

'알고리즘(코딩테스트)' 카테고리의 다른 글

[BFS] 개념(Breadth First Search; 너비 우선 탐색) - 자바스크립트  (0) 2025.02.16
큐(Queue) 구현 및 테스트 (JavaScript, Python)  (0) 2025.02.16
[DFS] 순열(permutation)  (0) 2025.02.16
[백준][DFS][난이도:하] 단지번호 붙이기 (2667번)  (0) 2025.02.16
[백준][DFS][난이도:하] 차이를 최대로 (10819번)  (0) 2025.02.16
반응형

1.  문제

■ DFS를 이용하여 리스트의 순열을 구현한다.

 

2. 핵심요약

■ DFS 알고리즘 활용법을 알아보자.

 

3. JavaScript 코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 주어진 배열 arr과 방문 여부를 추적할 visited 배열을 초기화
let arr = [1, 2, 3, 4, 5];
let visited = new Array(arr.length).fill(false); // arr 길이만큼 false로 채운 배열 생성
 
let result = []; // 결과를 저장할 배열
 
// 깊이 우선 탐색(DFS)을 수행하는 함수
const dfs = (depth) => {
    // 종료 조건: 모든 원소를 선택했을 때
    if (depth === arr.length) {
        console.log(result); // 결과 배열을 출력
        return result; // 결과 반환
    }
 
    // 배열의 각 원소를 순차적으로 처리
    for (let i = 0; i < arr.length; i++) {
        // 이미 방문한 원소는 건너뜀
        if (visited[i]) continue;
 
        visited[i] = true; // 현재 원소를 방문 처리
        result.push(arr[i]); // 결과 배열에 현재 원소 추가
 
        // 재귀적으로 DFS 호출 (다음 깊이로 이동)
        dfs(depth + 1);
 
        // 재귀 호출 후, 백트래킹: 방문을 해제하고, 결과에서 현재 원소를 제거
        visited[i] = false;
        result.pop();
    }
}
 
// DFS 탐색 시작
dfs(0);
 
 cs

 

4. 참고

https://languagestory.tistory.com/380

 

[DFS] 개념(Depth First Search; 깊이 우선 탐색) - 자바스크립트

1. DFS(Depth First Search; 깊이 우선 탐색)의 개념■ 그래프에서 모든 노드를 한번씩 탐색하기 위한 방법■ 스택 또는 재귀함수를 이용하여 구현■ 루트 노드[또는 임의의 노드]에서 시작하여 형제(si

languagestory.tistory.com

 

반응형
저작자표시

'알고리즘(코딩테스트)' 카테고리의 다른 글

[BFS] 개념(Breadth First Search; 너비 우선 탐색) - 자바스크립트  (0) 2025.02.16
큐(Queue) 구현 및 테스트 (JavaScript, Python)  (0) 2025.02.16
[백준][DFS][난이도:하] 단지번호 붙이기 (2667번)  (0) 2025.02.16
[백준][DFS][난이도:하] 차이를 최대로 (10819번)  (0) 2025.02.16
[백준][DFS][난이도:하] 바이러스 (2606번)  (0) 2025.02.16
반응형

1.  문제

■ URL : https://www.acmicpc.net/problem/2667

■ 난이도 : 하 (DFS 기본문제)

 

2. 핵심요약

■ 문제유형 : 깊이우선탐색(DFS) 알고리즘

 

3. 문제풀이 접근

■ 시작점을 기준으로 상/하/좌/우 깊이 탐색 방법을 구현할 수 있어야 한다.

 

4. JavaScript 코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// 로컬 환경에서 입력을 받을지, stdin에서 받을지 결정하는 변수
let isLocal = true;
 
let fs = require('fs'); // 파일 시스템 모듈을 사용하여 파일 읽기
let input;
 
// 로컬 환경일 경우 파일에서 입력을 읽어옴, 그렇지 않으면 stdin에서 읽어옴
if (isLocal) {
    input = fs.readFileSync('./2667.txt').toString().split('\n'); // 파일에서 입력 받기
} else {
    input = fs.readFileSync('/dev/stdin').toString().split('\n'); // stdin에서 입력 받기
}
 
// 첫 번째 줄: 집합의 크기(size) 입력 받기
let size = Number(input[0]); // size: 지도(그래프)의 크기 (N x N)
 
// 그래프 초기화: 각 셀을 1 또는 0으로 나타내는 지도 배열
let graph = [];
for (let i = 1; i <= size; i++) {
    /*
    input[i]: input 배열에서 i번째 요소를 가져온다. 이 요소는 문자열.
    split(''): 문자열을 각 문자(또는 char) 단위로 쪼갠 후 배열로 변환.
    예를 들어, "123"은 ['1', '2', '3'] 배열로 변환.
    map(Number): 배열의 각 요소들을 map()을 사용하여 Number로 변환.
    */
    graph.push(input[i].split('').map(Number)); // 각 줄을 숫자로 변환하여 그래프에 추가
}
 
// 깊이 우선 탐색(DFS) 함수 정의
const dfs = (graph, i, j) => {
    // 주어진 좌표(i, j)가 그래프의 범위를 벗어나면 종료
    if (i < 0 || i >= size || j < 0 || j >= size) return false;
 
    // 현재 위치가 0인 경우(빈 집이거나 이미 방문한 곳)라면 종료
    if (!graph[i][j]) return false;
 
    // 현재 위치를 방문 처리 (1 -> 0으로 변경)
    graph[i][j] = 0;
    complexSize += 1; // 복잡한 구역의 크기 증가
 
    // 상, 하, 좌, 우로 인접한 집들을 방문
    dfs(graph, i-1, j, complexSize);    // 상
    dfs(graph, i+1, j, complexSize);    // 하
    dfs(graph, i, j-1, complexSize);    // 좌
    dfs(graph, i, j+1, complexSize);    // 우
 
    return true; // 새로운 단지 발견
}
 
// 단지 크기를 저장할 배열
let answer = [];
let complexSize; // 단지 크기 변수
 
// 모든 지점에 대해 DFS 수행
for (let i = 0; i < size; i++) {
    for (let j = 0; j < size; j++) {
        complexSize = 0; // 각 단지를 탐색할 때마다 크기 초기화
        // 만약 DFS 탐색을 통해 단지가 발견되면 (현재 위치가 1인 경우)
        if (dfs(graph, i, j)) {
            answer.push(complexSize); // 해당 단지 크기 기록
        }
    }
}
 
// 단지 크기를 오름차순으로 정렬
answer.sort((a, b) => a - b);
 
// 결과 출력
console.log(answer.length + "\n" + answer.join("\n")); // 단지의 개수와 각 단지의 크기 출력
 
 cs

 

5. 참고

https://languagestory.tistory.com/380

 

[DFS] 개념(Depth First Search; 깊이 우선 탐색) - 자바스크립트

1. DFS(Depth First Search; 깊이 우선 탐색)의 개념■ 그래프에서 모든 노드를 한번씩 탐색하기 위한 방법■ 스택 또는 재귀함수를 이용하여 구현■ 루트 노드[또는 임의의 노드]에서 시작하여 형제(si

languagestory.tistory.com

 

반응형
저작자표시

'알고리즘(코딩테스트)' 카테고리의 다른 글

큐(Queue) 구현 및 테스트 (JavaScript, Python)  (0) 2025.02.16
[DFS] 순열(permutation)  (0) 2025.02.16
[백준][DFS][난이도:하] 차이를 최대로 (10819번)  (0) 2025.02.16
[백준][DFS][난이도:하] 바이러스 (2606번)  (0) 2025.02.16
[백준][DFS][난이도:하] 노드사이의 거리 (1240번)  (1) 2025.02.16
반응형

1.  문제

■ URL : https://www.acmicpc.net/problem/2606

■ 난이도 : 하 (DFS 기본문제)

 

2. 핵심요약

■ 예제입력

    - 첫째 줄: 컴퓨터의 수 → 노드 수
    - 둘째 줄: 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수 → 간선의 수
    - 셋째 줄이하 : 간선 정보

7
6
1 2
2 3
1 5
5 2
5 6
4 7

 

■ "예제 입력"을 "그래프"로 표현

 

■ "그래프"를 "인접리스트"로 표현

0  
1 2, 5
2 1, 3, 5
3 2
4 7
5 1, 2, 6
6 5
7 4

 

3. 문제풀이 접근

■ 그래프에서 1번 노드를 시작으로 연결된 모든 노드의 갯수를 카운트한다. (DFS, BFS)

 

4. JavaScript 코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// 로컬 환경에서 입력을 받을지, stdin에서 받을지 결정하는 변수
let isLocal = true;
 
let fs = require('fs'); // 파일 시스템 모듈을 사용하여 파일 읽기
let input;
 
// 로컬 환경일 경우 파일에서 입력을 읽어옴, 그렇지 않으면 stdin에서 읽어옴
if (isLocal) {
    input = fs.readFileSync('./2606.txt').toString().split('\n'); // 파일에서 입력 받기
} else {
    input = fs.readFileSync('/dev/stdin').toString().split('\n'); // stdin에서 입력 받기
}
 
// 첫 번째 줄: 노드의 개수(nodeCnt)와 간선의 개수(edgeCnt) 입력 받기
let nodeCnt = Number(input[0]); // nodeCnt: 노드의 개수
let edgeCnt = Number(input[1]); // edgeCnt: 간선의 개수
 
// 그래프 초기화 (1): 각 노드에 연결된 다른 노드들을 저장할 배열
// let graph = Array(nodeCnt + 1).fill([]); // 이렇게 하면 모든 항목이 동일한 배열을 참조하게 되어 문제가 발생할 수 있음
// 위와 같은 방식은 각 항목이 동일한 참조를 가지므로, 하나의 항목을 수정하면 다른 항목에 영향이 미친다.
 
// 그래프 초기화 (2): 각 항목에 대해 별도의 빈 배열을 할당하여 독립적인 배열을 생성한다.
// 각 항목에 대해 별도의 빈 배열을 할당하여 독립적인 배열을 생성하므로, 수정이 다른 항목에 영향을 주지 않는다.
graph = [];
for (let i = 0; i < nodeCnt + 1; i++) {
    graph[i] = [];      // 각 노드에 연결된 다른 노드들을 저장할 빈 배열 생성
}
 
// visited 초기화
// fill()을 사용하여 참조형 값(객체나 배열)을 채우는 경우, 그 참조가 모든 배열 요소에 적용된다.
// 즉, 객체나 배열을 채우면 모든 항목이 동일한 객체나 배열을 참조한다.
// 반면, true나 false 같은 원시 값은 값 자체가 할당되기 때문에 배열 내의 각 요소는 서로 독립적으로 존재한다.
let visited = Array(nodeCnt + 1).fill(false);       // 방문 여부를 추적하는 배열 (각 노드는 방문되지 않은 상태로 시작)
 
// input 데이터를 읽고 그래프에 간선 정보를 추가
const START_LINE = 2; // 간선 정보는 2번째 줄부터 시작
for (let i = START_LINE; i < START_LINE + edgeCnt; i++) {
    let [nodeSrc, nodeDst] = input[i].split(' ').map(Number);   // 간선의 두 노드
    graph[nodeSrc].push(nodeDst);   // nodeSrc와 nodeDst를 연결
    graph[nodeDst].push(nodeSrc);   // nodeDst와 nodeSrc를 연결 (무방향 그래프)
}
 
 // 감염된 노드의 수를 저장할 변수
let answer = 0;
 
// 깊이 우선 탐색(DFS) 함수
const dfs = (graph, currNode, visited) => {
    visited[currNode] = true; // 현재 노드를 방문 처리
    answer += 1; // 현재 노드를 감염된 노드로 카운트
 
    // 현재 노드와 연결된 다른 노드들에 대해 재귀적으로 DFS 호출
    for (nextNode of graph[currNode]) {
        if (!visited[nextNode]) { // 아직 방문하지 않은 노드에 대해 DFS 탐색
            dfs(graph, nextNode, visited);
        }
    }
}
 
// 노드 1에서 시작하여 DFS를 실행 (노드 1부터 감염이 시작된다고 가정)
dfs(graph, 1, visited);
 
// 출력: 감염된 노드 수에서 시작 노드(1번 노드)를 제외하고 출력
console.log('감염된 Node 수:', answer - 1); // 시작 노드를 제외한 감염된 노드 수 출력
 
 cs

 

5. 참고

https://languagestory.tistory.com/380

 

[DFS] 개념(Depth First Search; 깊이 우선 탐색) - 자바스크립트

1. DFS(Depth First Search; 깊이 우선 탐색)의 개념■ 그래프에서 모든 노드를 한번씩 탐색하기 위한 방법■ 스택 또는 재귀함수를 이용하여 구현■ 루트 노드[또는 임의의 노드]에서 시작하여 형제(si

languagestory.tistory.com

 

반응형
저작자표시

'알고리즘(코딩테스트)' 카테고리의 다른 글

[백준][DFS][난이도:하] 단지번호 붙이기 (2667번)  (0) 2025.02.16
[백준][DFS][난이도:하] 차이를 최대로 (10819번)  (0) 2025.02.16
[백준][DFS][난이도:하] 노드사이의 거리 (1240번)  (1) 2025.02.16
[백준][DFS][난이도:하] 유기농 배추 (1012번)  (0) 2025.02.16
[DFS] 개념(Depth First Search; 깊이 우선 탐색) - 자바스크립트  (1) 2025.02.16
반응형

1.  문제

■ URL : https://www.acmicpc.net/problem/1240

■ 난이도 : 하 (DFS 기본문제)

 

2. 핵심요약

■ 문제유형 : 깊이우선탐색(DFS) 알고리즘

 

3. 문제풀이 접근

■ distance 벡터[리스트]를 사용하여 누적되는 비용을 계산한다.

 

4. JavaScript 코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// 로컬 환경에서 입력을 받을지, stdin에서 받을지 결정하는 변수
let isLocal = true;
 
let fs = require('fs'); // 파일 시스템 모듈을 사용하여 파일 읽기
let input;
 
// 로컬 환경일 경우 파일에서 입력을 읽어옴, 그렇지 않으면 stdin에서 읽어옴
if (isLocal) {
    input = fs.readFileSync('./1240.txt').toString().split('\n');   // 파일에서 입력 받기
} else {
    input = fs.readFileSync('/dev/stdin').toString().split('\n');   // stdin에서 입력 받기
}
 
// 첫 번째 줄: 노드의 개수(N)와 거리를 알고 싶은 노드 쌍의 개수(M) 입력 받기
let [n, m] = input[0].split(' ').map(Number);
 
// 그래프 초기화: 각 노드에 연결된 노드와 거리를 저장할 배열
let graph = [];
for (let i = 0; i <= n; i++) {  // index 0은 사용하지 않음
    graph[i] = [];              // 각 노드에 연결된 노드들을 저장할 배열 초기화
}
 
// 트리 상에 연결된 두 점과 거리를 입력 받아 그래프에 저장
for (let i = 1; i < n; i++) {
    const [s, d, c] = input[i].split(' ').map(Number);  // s: 시작 노드, d: 도착 노드, c: 거리
    graph[s].push([d, c]);  // s 노드에서 d 노드까지 거리 c로 연결
    graph[d].push([s, c]);  // d 노드에서 s 노드까지 거리 c로 연결 (무방향 그래프)
}
 
// 깊이 우선 탐색(DFS) 함수
const dfs = (graph, currNode, dist, visited, distance) => {
    // 현재 노드가 이미 방문된 노드라면 탐색 종료
    if (visited[currNode]) return;
 
    visited[currNode] = true;   // 현재 노드를 방문 처리
    distance[currNode] = dist;  // 현재 노드까지의 거리 기록
 
    // 현재 노드와 연결된 노드들을 탐색
    for ([nextNode, cost] of graph[currNode]) {
        dfs(graph, nextNode, dist + cost, visited, distance); // 연결된 노드로 재귀 호출
    }
}
 
// M개의 거리 요청에 대해 각각의 거리를 계산
for (let i = n; i < n + m; i++) {
    const [s, d] = input[i].split(' ').map(Number); // s: 시작 노드, d: 도착 노드
 
    // 방문 여부를 추적할 배열과 거리 배열 초기화
    let visited = new Array(n + 1).fill(false);     // 방문 여부 배열 (index 0은 사용하지 않음)
    let distance = new Array(n + 1).fill(0);        // 거리 배열 (index 0은 사용하지 않음)
 
    // 시작 노드(s)에서 DFS 시작, 거리 초기값은 0
    dfs(graph, s, 0, visited, distance);
 
    // 도착 노드(d)까지의 거리 출력
    console.log(distance[d]);
}
 
 cs

 

5. 참고

https://languagestory.tistory.com/380

 

[DFS] 개념(Depth First Search; 깊이 우선 탐색) - 자바스크립트

1. DFS(Depth First Search; 깊이 우선 탐색)의 개념■ 그래프에서 모든 노드를 한번씩 탐색하기 위한 방법■ 스택 또는 재귀함수를 이용하여 구현■ 루트 노드[또는 임의의 노드]에서 시작하여 형제(si

languagestory.tistory.com

 

반응형
저작자표시

'알고리즘(코딩테스트)' 카테고리의 다른 글

[백준][DFS][난이도:하] 차이를 최대로 (10819번)  (0) 2025.02.16
[백준][DFS][난이도:하] 바이러스 (2606번)  (0) 2025.02.16
[백준][DFS][난이도:하] 유기농 배추 (1012번)  (0) 2025.02.16
[DFS] 개념(Depth First Search; 깊이 우선 탐색) - 자바스크립트  (1) 2025.02.16
[백준] 주유소  (0) 2024.10.05
반응형

1.  문제

■ URL : https://www.acmicpc.net/problem/1012

■ 난이도 : 하 (DFS 기본문제)

 

2. 핵심요약

■ 예제입력

    - 첫번째 줄: Test Case
    - 두번째 줄: 10행 8열, 17개의 배추

    - 세번째 줄 이하: 17개 배추의 위치 (행 열)

2
10 8 17
0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6
10 10 1
5 5

 

■ "예제 입력"을 "그래프"로 표현

    - 0: 배추가 없는 곳
    - 1: 배추를 심은 곳

 

3. 문제풀이 접근

■ (0행 0열)부터 시작하여 (M형 N열)까지 순차적으로 하나씩 DFS를 수행한다. (모든 위치에서 시작)

■ DFS 수행 중 탐색이 처리된 위치는 visited 방문 기록을 남긴다.

■ DFS 수행이 1회라도 된 위치는 answer 횟수를 1회 증가한다.

 

4. JavaScript 코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
let isLocal = true          // 로컬 환경에서 입력을 받을지, stdin에서 받을지 결정하는 변수
 
let fs = require('fs');     // 파일 시스템 모듈을 사용하여 파일 읽기
let input;
 
if (isLocal) {
    input = fs.readFileSync('./1012.txt').toString().split('\n'); // 파일에서 입력 받기
} else {
    input = fs.readFileSync('/dev/stdin').toString().split('\n'); // stdin에서 입력 받기
}
 
// 깊이 우선 탐색(DFS) 함수
const dfs = (graph, currY, currX, rowSize, colSize) => {
    // 현재 위치가 유효한지, 범위 밖이면 종료
    if (currY < 0 || currY >= rowSize || currX < 0 || currX >= colSize) return false;
 
    // 현재 위치에 양배추가 없으면 종료
    if (graph[currY][currX] == 0) return false;
 
    // 현재 위치의 양배추를 방문 처리
    graph[currY][currX] = 0;
 
    // 상, 하, 좌, 우로 DFS 탐색
    dfs(graph, currY-1, currX, rowSize, colSize);   // 현재위치 기준 상
    dfs(graph, currY+1, currX, rowSize, colSize);   // 현재위치 기준 하
    dfs(graph, currY, currX-1, rowSize, colSize);   // 현재위치 기준 좌
    dfs(graph, currY, currX+1, rowSize, colSize);   // 현재위치 기준 우
 
    return true;    // 연결된 양배추를 모두 방문한 후 true 반환
}
 
// 테스트 케이스의 수를 첫 번째 줄에서 읽어옴
let testCase = Number(input[0]);
let nextCase = 1;
 
// 각 테스트 케이스에 대해 처리
while (testCase--) {
    // 각 테스트 케이스의 크기 및 양배추 개수를 읽어옴
    const [rowSize, colSize, cabageCnt] = input[nextCase].split(' ').map(Number);
 
    // 주어진 크기(rowSize, colSize)로 graph 초기화 (모두 0으로 초기화)
    let graph = [];
    for (let y = 0; y < rowSize; y++) {
        let graphRow = new Array(colSize).fill(0); // 각 행을 0으로 초기화
        graph.push(graphRow);
    }
 
    // 양배추가 있는 위치를 graph에 설정
    for (let i = 1; i <= cabageCnt; i++) {
        const [cabageY, cabageX] = input[nextCase + i].split(' ').map(Number);
        graph[cabageY][cabageX] = 1;    // 양배추가 있는 곳을 1로 설정
    }
 
    let answer = 0; // 연결된 양배추 군집 수
 
    // 그래프에서 모든 칸을 탐색
    for (let y = 0; y < rowSize; y++) {
        for (let x = 0; x < colSize; x++) {
            // (y, x) 위치에서 양배추가 있으면 DFS 탐색
            if (dfs(graph, y, x, rowSize, colSize)) {
                answer += 1; // 연결된 양배추 군집을 발견할 때마다 카운트 증가
            }
        }
    }
 
    // 각 테스트 케이스 결과 출력
    console.log(answer);
 
    // 다음 테스트 케이스로 넘어갈 때, 양배추 개수 + 1을 더하여 다음 입력 시작 위치로 이동
    nextCase += cabageCnt + 1;
}
 
 cs

 

 

5. 참고

https://languagestory.tistory.com/380

 

[DFS] 개념(Depth First Search; 깊이 우선 탐색) - 자바스크립트

1. DFS(Depth First Search; 깊이 우선 탐색)의 개념■ 그래프에서 모든 노드를 한번씩 탐색하기 위한 방법■ 스택 또는 재귀함수를 이용하여 구현■ 루트 노드[또는 임의의 노드]에서 시작하여 형제(si

languagestory.tistory.com

 

반응형
저작자표시

'알고리즘(코딩테스트)' 카테고리의 다른 글

[백준][DFS][난이도:하] 바이러스 (2606번)  (0) 2025.02.16
[백준][DFS][난이도:하] 노드사이의 거리 (1240번)  (1) 2025.02.16
[DFS] 개념(Depth First Search; 깊이 우선 탐색) - 자바스크립트  (1) 2025.02.16
[백준] 주유소  (0) 2024.10.05
[백준] 수들의 합  (0) 2024.10.05
반응형

1. DFS(Depth First Search; 깊이 우선 탐색)의 개념

■ 그래프에서 모든 노드를 한번씩 탐색하기 위한 방법

■ 스택 또는 재귀함수를 이용하여 구현

■ 루트 노드[또는 임의의 노드]에서 시작하여 형제(sibling) 노드로 넘어가기 전에 시작한 분기의 마지막 노드까지 깊게 탐색하는 방법

 

2. DFS 노드 방문 순서

■ 결과 : 1 → 2 → 4 → 5 → 6 → 3 → 7 → 10 → 8 → 9

    - step1) 도달 가능한 마지막 노드(막다른 길)까지 이동한다.

    - step2) 지나처 온 최근 갈림길(형제노드)로 되돌아 간다.

    - step3) 모든 노드를 탐색할 때까지 step1과 step2를 반복한다.

 

3. 그래프 표현

■ "그래프"는 "인접 리스트"로 표현하여 보다 이해하기 쉬운 형태로 만들 수 있다.

1 2, 3
2 1, 4
3 1, 7, 8, 9
4 2, 5, 6
5 4
6 4
7 3, 10
8 3
9 3
10  

 

■ "인접 리스트"는 "2차원 배열[리스트]" 또는 "테이블[dictionary]" 자료구조로 코드화 한다.

1
2
3
4
5
6
7
8
9
10
11
12
let graph = []
graph['0'] = []         // index 0: 사용하지 않음.
graph['1'] = ['2', '3']
graph['2'] = ['1', '4']
graph['3'] = ['1', '7', '8', '9']
graph['4'] = ['2', '5', '6']
graph['5'] = ['4']
graph['6'] = ['4']
graph['7'] = ['3', '10']
graph['8'] = ['3']
graph['9'] = ['3']
graph['10'] = ['7']
 cs

 

4. JavaScript 코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 깊이우선탐색(DFS) 함수
const dfs = (graph, currNode, visited = []) => {
  
  visited[currNode] = true;   // 현재 노드 방문 처리
  console.log(currNode);      // 현재 노드 출력
 
  // 현재 노드와 연결된 다른 노드들에 대해 탐색
  for (let nextNode of graph[currNode]) {
      if (!visited[nextNode]) {           // 아직 방문하지 않은 노드에 대해서만 재귀 호출
          dfs(graph, nextNode, visited);  // 재귀 호출로 다음 노드 탐색
      }
  }
}
 
dfs(graph, '1')        // 노드1 부터 깊이우선탐색(DFS) 시작
 
 cs

 

반응형
저작자표시

'알고리즘(코딩테스트)' 카테고리의 다른 글

[백준][DFS][난이도:하] 노드사이의 거리 (1240번)  (1) 2025.02.16
[백준][DFS][난이도:하] 유기농 배추 (1012번)  (0) 2025.02.16
[백준] 주유소  (0) 2024.10.05
[백준] 수들의 합  (0) 2024.10.05
[백준] 설탕 배달  (0) 2024.10.04

+ Recent posts

티스토리툴바