그래프 (DFS) 문제#1

그래프 DFS 문제풀이

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

문제

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

1 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 1 1 0 0 0 1 1 1
0 0 0 0 1 0 0 1 1 1
입력
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

---

풀이 방향

• 가로 세로 길이를 이용해서 2차원 배열을 만든다.
• 배추의 위치를 확인하여 해당하는 2차원 배열의 위치에 1을 넣어준다.
• dfs를 이용해서 1이 최초로 위치한 지점에서, 멈추고 상하좌우를 탐색해서 0으로 바꿔줘서 방문 표시를 한다.
• 그리고 다시 배추밭을 순회아여 dfs를 반복해서 필요 벌레수를 증가시킨다.

코드

function countWorms(m, n, positions) {
  // 배추밭을 초기화
  const field = Array.from({ length: n }, () => Array(m).fill(0));

  // 배추 위치에 1을 표시
  for (let [x, y] of positions) {
    field[y][x] = 1;
  }

  // 이동 방향 (상, 하, 좌, 우)
  const directions = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];

  function dfs(x, y) {
    // 현재 위치 방문 표시
    field[y][x] = 0;

    // 상하좌우 탐색
    for (let [dx, dy] of directions) {
      const nx = x + dx;
      const ny = y + dy;

      // 인접한 배추가 있으면 그곳을 탐색
      if (nx >= 0 && nx < m && ny >= 0 && ny < n && field[ny][nx] === 1) {
        dfs(nx, ny);
      }
    }
  }

  let wormCount = 0;

  // 배추밭을 순회하며 지렁이가 필요한 구역을 탐색
  for (let y = 0; y < n; y++) {
    for (let x = 0; x < m; x++) {
      if (field[y][x] === 1) {
        dfs(x, y);
        wormCount++;
      }
    }
  }

  return wormCount;
}

function solution(input) {
  const lines = input.trim().split("\n");
  const T = parseInt(lines[0], 10);
  let result = [];
  let index = 1;

  for (let i = 0; i < T; i++) {
    const [M, N, K] = lines[index].split(" ").map(Number);
    let positions = [];

    for (let j = 0; j < K; j++) {
      const [X, Y] = lines[index + 1 + j].split(" ").map(Number);
      positions.push([X, Y]);
    }

    result.push(countWorms(M, N, positions));
    index += K + 1;
  }

  console.log(result.join("\n"));
}

/*
---
T => 테스트 케이스의 갯수
---
M => 가로 길이
N => 세로 길이
K => 배추의 갯수
*/

// 예제 입력
const input = `1
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
`;
solution(input);

---

마무리

• DFS의 개념을 알고서 , 문제에 접근했다.
• 그러나 ,아직 혼자서 문제를 해결하기까지는 미숙한 것 같다.
• 이번에 GPT와 유튜브 시청을 통해서 DFS를 이해하는데 좀 더 신경을 썼다.