[DFS] 유기농배추

[ericagong]

⭐ 성찰

1. ⭐ 모든 좌표에 대해 DFS가 정상 종료되는 수를 카운트 -> DFS는 모든 재귀 호출이 종료될 때, 정상 종료되므로 맨 마지막 return 문에서만 true 반환하도록 처리

❓ 문제 상황

유기농 배추

👨‍💻 문제 해결: 풀이 방식

✅ 1차 풀이: 키워드

1. ⭐ 모든 좌표에 대해 DFS가 정상 종료되는 수를 카운트
2. 기존 그래프 외에 별도의 자료구조를 만들지 않고, 그래프 특정 위치값을 방문시 다른 값으로 변경하기

   
   // https://www.acmicpc.net/problem/1012

const fs = require("fs"); const inputs = fs.readFileSync("/dev/stdin").toString().split("\n");

const T = Number(inputs.shift());

function log(graph) { for (let i = 0; i < graph.length; i++) { console.log(graph[i].join(" ")); } console.log(); }

const dx = [-1, 1, 0, 0]; const dy = [0, 0, -1, 1]; function dfs(x, y, g, N, M) { // 범위 벗어나면 정상 종료 X if (x < 0 || y < 0 || x >= N || y >= M) return false;

if (g[x][y] === 0) return false; if (g[x][y] === 2) return false;

// 방문처리 g[x][y] = 2;

// 상하좌우에 대해 재귀호출 for (let i = 0; i < 4; i++) { const nx = x + dx[i]; const ny = y + dy[i]; dfs(nx, ny, g, N, M); }

// 정상 종료 return true; }

let time = 0; while (time < T) { time += 1; const [M, N, K] = inputs.shift().split(" ").map(Number); const g = Array.from({ length: N }, () => new Array(M).fill(0));

for (let i = 0; i < K; i++) { const [y, x] = inputs.shift().split(" ").map(Number); g[x][y] = 1; }

let cnt = 0; for (let i = 0; i < N; i++) { for (let j = 0; j < M; j++) { if (dfs(i, j, g, N, M)) cnt += 1; } }

console.log(cnt); }