반응형

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. BFS(Breadth First Search; 너비 우선 탐색)의 개념

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

■ 루트 노드[또는 임의의 노드]에서 시작하여, 형제(sibling) 노드를 탐색한 후, 각 레벨에 있는 노드를 차례대로 탐색하는 방법.

■ Queue를 이용하여 구현

 

2. BFS 노드 방문 순서

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

    - 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 코딩

- JavaScript로 구현한 Queue 참고: https://languagestory.tistory.com/400

 

큐(Queue) 구현 및 테스트 (JavaScript, Python)

1.  Queue 개념■ 선입선출 (FIFO): 큐에서 데이터는 먼저 들어온 순서대로 출력된다.■ enqueue: 큐에 데이터를 삽입하는 작업■ dequeue: 큐에서 데이터를 제거하는 작업■ Front: 큐의 앞쪽 (데이터가

languagestory.tistory.com

 

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
// 'queue.js' 파일에서 Queue 클래스를 가져옴
const Queue = require('./queue.js');
 
// BFS 알고리즘 구현
const bfs = (graph, currNode, visited) => {
 
    // Queue 인스턴스를 생성하여 사용
    const queue = new Queue();
 
    // 시작 노드를 큐에 추가하고 방문처리
    queue.enqueue(currNode);
    visited[currNode] = true;
 
    // 큐가 비어있지 않으면 계속해서 탐색
    while (queue.getLength() > 0) {         // 큐가 빌 때까지 반복
        const nextNode = queue.dequeue();   // 큐에서 하나의 노드를 꺼냄 (이 노드를 탐색)
        console.log(nextNode);               // 현재 노드를 출력 (탐색한 노드)
 
        // 꺼낸 노드의 인접 노드들을 탐색
        for (const neighborNode of graph[nextNode]) {
            // 방문하지 않은 인접 노드가 있으면 큐에 추가하고 방문처리
            if (!visited[neighborNode]) {
                queue.enqueue(neighborNode);  // 큐에 인접 노드를 추가
                visited[neighborNode] = true; // 해당 노드를 방문했다고 표시
            }
        }
    }
}
 
// 그래프의 연결 정보 (인접 리스트 형태로 표현)
const graph = [
    [],                 // 0번 노드: 사용하지 않음
    [2, 3, 4],          // 1번 노드: 2, 3, 4번 노드와 연결
    [1],                // 2번 노드: 1번 노드와 연결
    [1, 5, 6],          // 3번 노드: 1, 5, 6번 노드와 연결
    [1, 7],             // 4번 노드: 1, 7번 노드와 연결
    [3, 8],             // 5번 노드: 3, 8번 노드와 연결
    [3],                // 6번 노드: 3번 노드와 연결
    [4],                // 7번 노드: 4번 노드와 연결
    [5]                 // 8번 노드: 5번 노드와 연결
]
 
// 방문 여부를 체크하는 배열 (그래프 크기만큼 false로 초기화)
const visited = Array(graph.length).fill(false);    
 
// 1번 노드부터 BFS 탐색 시작
bfs(graph, 1, visited);     // 1번 노드부터 BFS 탐색
 
 cs

 

반응형
저작자표시

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

[DFS] 조합(combination)  (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.  Queue 개념

■ 선입선출 (FIFO): 큐에서 데이터는 먼저 들어온 순서대로 출력된다.

■ enqueue: 큐에 데이터를 삽입하는 작업

■ dequeue: 큐에서 데이터를 제거하는 작업

■ Front: 큐의 앞쪽 (데이터가 제거되는 곳)

■ Rear[또는 Tail]: 큐의 뒤쪽 (새로운 데이터가 추가되는 곳)

 

2. 핵심요약

■ BFS (너비 우선 탐색, Breadth-First Search) 알고리즘에서는 Queue 자료구조가 필수적으로 활용된다.

■ BFS는 그래프나 트리에서 시작 노드에서부터 인접한 노드들을 차례대로 방문하여 탐색을 진행한다.

■ 이때 선입선출(FIFO) 방식이 BFS 탐색의 특성과 잘 맞아떨어지기 때문에 Queue 자료구조를 사용한다.

 

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// Queue 클래스를 정의
class Queue {
    // 생성자: Queue 클래스 인스턴스를 생성할 때 실행됨
    constructor() {
        this.items = {};        // 데이터를 저장할 객체, index를 키로 사용하여 값들을 저장
        this.headIndex = 0;     // 큐의 앞부분을 나타내는 인덱스
        this.tailIndex = 0;     // 큐의 뒷부분을 나타내는 인덱스
    }
    
    // 큐에 아이템을 추가하는 메소드
    enqueue(item) {
        this.items[this.tailIndex] = item;  // tailIndex 위치에 item을 추가
        this.tailIndex++;                   // tailIndex를 증가시켜 큐의 끝을 업데이트
    }
    
    // 큐에서 아이템을 제거하는 메소드
    dequeue() {
        const item = this.items[this.headIndex];    // headIndex 위치에서 아이템을 가져옴
        delete this.items[this.headIndex];          // 해당 위치의 아이템을 삭제하여 메모리에서 제거
        this.headIndex++;           // headIndex를 증가시켜 큐의 앞부분을 업데이트
        return item;                // 제거된 아이템을 반환
    }
 
    // 큐의 앞부분에 있는 아이템을 반환하는 메소드 (삭제하지 않음)
    peek() {
        return this.items[this.headIndex];         // headIndex 위치의 아이템을 반환
    }
 
    // 큐에 있는 아이템의 개수를 반환하는 메소드
    getLength() {
        return this.tailIndex - this.headIndex;   // 큐에 남아있는 아이템의 개수를 계산
    }
}
 
// Queue 클래스를 외부 모듈로 내보내기
module.exports = Queue;
 
// 큐 인스턴스를 생성
let queue = new Queue();
queue.enqueue(5);       // 큐: 5
queue.enqueue(3);       // 큐: 5, 3
queue.dequeue();        // 큐: 3
queue.enqueue(4);       // 큐: 3, 4
queue.enqueue(1);       // 큐: 3, 4, 1
queue.dequeue();        // 큐: 4, 1
queue.enqueue(7);       // 큐: 4, 1, 7
queue.enqueue(6);       // 큐: 4, 1, 7, 6
queue.dequeue();        // 큐: 1, 7, 6
 
// 큐가 비어있지 않으면 계속해서 dequeue를 통해 큐의 모든 아이템을 출력
while (queue.getLength() > 0) {
    console.log(queue.dequeue());  // 큐의 앞부분 아이템을 출력 후 제거
}
 
 cs

 

4. 파이썬 코딩

■ Python에서는 collections.deque를 사용하여 큐 자료구조를 구현할 수 있다.

■ deque는 **덱(Deque, Double-ended Queue)**을 구현한 자료구조로, 큐와 스택 모두에 효율적으로 사용할 수 있다.

■ deque는 큐의 앞과 뒤에서 삽입과 삭제가 모두 효율적이기 때문에 큐 구현에 매우 적합하다.

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
from collections import deque
 
class Queue:
    def __init__(self):
        self.items = deque()
 
    def enqueue(self, item):
        self.items.append(item)  # 큐에 아이템 추가 (뒤에 추가)
 
    def dequeue(self):
        if self.get_length() > 0:
            return self.items.popleft()  # 큐에서 아이템 제거 (앞에서 제거)
        return None  # 큐가 비었을 경우 None 반환
 
    def peek(self):
        if self.get_length() > 0:
            return self.items[0]  # 큐의 첫 번째 아이템 확인 (삭제하지 않음)
        return None
 
    def get_length(self):
        return len(self.items)  # 큐의 크기 반환
 
# Test
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.dequeue()
queue.enqueue(4)
queue.enqueue(5)
queue.enqueue(6)
queue.dequeue()
 
while queue.get_length() > 0:
    print(queue.dequeue())
 
 cs

 

반응형
저작자표시

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

[DFS] 조합(combination)  (0) 2025.02.16
[BFS] 개념(Breadth First Search; 너비 우선 탐색) - 자바스크립트  (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/10819

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

 

2. 핵심요약

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

 

3. 문제풀이 접근

■ 선행학습 : DFS를 이용하여 리스트의 순열을 구현할 수 있어야 한다.

    - 참고: https://languagestory.tistory.com/403

 

[DFS] 순열(permutation)

1.  문제■ DFS를 이용하여 리스트의 순열을 구현한다. 2. 핵심요약■ DFS 알고리즘 활용법을 알아보자. 3. JavaScript 코딩12345678910111213141516171819202122232425262728293031323334// 주어진 배열 arr과 방문 

languagestory.tistory.com

 

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
// 로컬 환경에서 입력을 받을지, stdin에서 받을지 결정하는 변수
let isLocal = true;
 
let fs = require('fs'); // 파일 시스템 모듈을 사용하여 파일 읽기
let input;
 
// 로컬 환경일 경우 파일에서 입력을 읽어옴, 그렇지 않으면 stdin에서 읽어옴
if (isLocal) {
    input = fs.readFileSync('./10819.txt').toString().split('\n'); // 파일에서 입력 받기
} else {
    input = fs.readFileSync('/dev/stdin').toString().split('\n'); // stdin에서 입력 받기
}
 
// 첫 번째 줄: 배열 A의 갯수 N을 입력 받기
let n = Number(input[0]);   // n: 배열 A의 크기
let arr = input[1].split(' ').map(Number); // 두 번째 줄: 배열 A의 원소들을 입력받아 arr 배열에 저장
let visited = new Array(n).fill(false); // 방문 여부를 추적하는 배열 (각 원소는 false로 초기화)
 
// 결과 변수 초기화: 가능한 값 중 가장 큰 값인 `max`를 구할 것
let max = -1e9; // `max`를 매우 작은 값으로 초기화
let result = []; // DFS에서 사용할 부분 배열
 
// 깊이 우선 탐색(DFS) 함수 정의
const dfs = (depth) => {
    // 종료 조건: 배열을 모두 탐색했다면
    if (depth === arr.length) {
        let sum = 0;
        
        // 배열이 완성되었으므로 인접한 원소들 간의 차이의 절댓값의 합을 구함
        for (let i = 0; i < n-1; i++) {
            sum += Math.abs(result[i] - result[i+1]); // 인접한 원소의 차이의 절댓값을 더함
            max = Math.max(max, sum); // 최대값을 갱신
        }
        return max; // 최대값을 반환
    }
 
    // 배열의 모든 원소에 대해 재귀적으로 DFS 탐색
    for (let i = 0; i < n; i++) {
        // 이미 방문한 원소는 다시 선택하지 않음
        if (visited[i]) continue;
 
        // 현재 원소를 방문하고 배열에 추가
        visited[i] = true;
        result.push(arr[i]);
 
        // 다음 원소를 탐색하기 위해 DFS 호출
        dfs(depth + 1);
 
        // 탐색을 마친 후, 방문을 해제하고 마지막 원소를 제거
        visited[i] = false;
        result.pop();
    }
}
 
// DFS 탐색 시작
dfs(0);
 
// 결과 출력: 가장 큰 차이 합을 출력
console.log(max);
 
 cs

 

5. 참고

https://languagestory.tistory.com/380

 

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

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

languagestory.tistory.com

 

반응형
저작자표시

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

[DFS] 순열(permutation)  (0) 2025.02.16
[백준][DFS][난이도:하] 단지번호 붙이기 (2667번)  (0) 2025.02.16
[백준][DFS][난이도:하] 바이러스 (2606번)  (0) 2025.02.16
[백준][DFS][난이도:하] 노드사이의 거리 (1240번)  (1) 2025.02.16
[백준][DFS][난이도:하] 유기농 배추 (1012번)  (0) 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

+ Recent posts

티스토리툴바