[백준][DFS][난이도:하] 유기농 배추 (1012번)

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

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;
}
 

 

5. 참고

https://languagestory.tistory.com/380

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