반응형

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] 자료구조로 정의할 수 있다.

 

4. 파이썬 코딩

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
def dfs(graph, start, visited = []):
    visited.append(start)
 
    for node in graph[start]:
        if node not in visited:
            dfs(graph, node, visited)
 
    return visited
 
 
if __name__ == '__main__':
    graph = dict() 
    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']
 
    result = dfs(graph, '1')
    print(result)
 cs

 

5. 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
function dfs(graph, v, visited = []) {
    
    visited[v] = true;
    console.log(v);
  
    for (let node of graph[v]) {
      if (!visited[node]) {
        dfs(graph, node, visited);
      }
    }
  }
 
 
graph = []
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']
 
result = dfs(graph, '1')
console.log(result)
 cs

 

 

반응형
저작자표시

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

큐(Queue) 구현 및 테스트 (JavaScript, Python)  (0) 2025.01.06
[백준] 주유소  (0) 2024.10.05
[백준] 수들의 합  (0) 2024.10.05
[백준] 설탕 배달  (0) 2024.10.04
[백준] 읽어버린 괄호  (0) 2024.10.04
반응형

1.  문제

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

 

2. 핵심요약

■ 1번째 Row : 사람의 수 N(1 ≤ N ≤ 1,000)

■ 2번째 Row : 각 사람이 돈을 인출하는데 걸리는 시간

1
2
5
3 1 4 3 2
 cs

 

3. 문제풀이 접근

■ 문제유형 : 탐욕(Greedy) 알고리즘

■ 최소 시간의 합을 구하기 위해서 점유시간이 낮은 사람부터 먼저 처리 되어야 한다.

 

4. 파이썬 코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
isTest = True
if isTest:
    f = open("./11399.txt", 'r')
    cnt = int(f.readline())
    occupy = list(map(int, f.readline().split()))
else:
    cnt = int(input())
    occupy = list(map(int, input().split()))
 
# 배열을 오름차순으로 정렬
occupy.sort()
 
sum = 0
answer = 0
for x in occupy:
    sum += x            # 각 사람이 (대기한 시간 + 돈을 인출하는데 걸리는 시간)
    answer += sum       # 각 사람이 (대기한 시간 + 돈을 인출하는데 걸리는 시간)의 누적합
 
print(answer)
 cs

 

5. JavaScript 코딩

■ 배열.sort()와 배열.sort((a, b) => a - b)의 정렬 방식 차이점

    - 배열.sort() : ['3', '12', '215']인 경우, ['12', '215', '3']으로 정렬된다.

    - 배열.sort((a, b) => a - b) : ['3', '12', '215']인 경우, ['3', '12', '215']으로 정렬된다.

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
let isTest = true
 
let fs = require('fs');
let input;
if (isTest) {
    input = fs.readFileSync('./11399.txt').toString().split('\n');
} else {
    input = fs.readFileSync('/dev/stdin').toString().split('\n');
}
 
let cnt = Number(input[0]);         // 사람 수
let occupy = [];                    // 각 사람이 돈을 인출하는데 걸리는 시간
for (let i = 0; i < cnt; i++) {
    occupy.push(Number(input[1].split(' ')[i]));
}
 
// 배열을 오름차순으로 정렬
occupy.sort((a, b) => a - b);
//occupy.sort()   // 위의 것과 차이점 중요
 
let sum = 0;
let answer = 0;
for (let i = 0; i < occupy.length; i++) {
    sum += occupy[i];       // 각 사람이 (대기한 시간 + 돈을 인출하는데 걸리는 시간)
    answer += sum;          // 각 사람이 (대기한 시간 + 돈을 인출하는데 걸리는 시간)의 누적합
}
 
console.log(answer);
 cs

 

 

반응형
저작자표시

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

[백준] 주유소  (0) 2024.10.05
[백준] 수들의 합  (0) 2024.10.05
[백준] 설탕 배달  (0) 2024.10.04
[백준] 읽어버린 괄호  (0) 2024.10.04
[백준] 동전 0  (0) 2024.10.03

+ Recent posts

티스토리툴바