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