반응형
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 |