백준 2667번

QUESTION LINK

그래프 순회를 이용해 해결해야하는 문제였습니다. 문제를 해결하기 위해 일종의 흐름을 짜는 과정이 필요했는데 그 과정은 아래와 같았습니다.

1. 그래프의 각 부분들(여기서는 box라는 이름으로 설정)을 순회하면서 그 값이 0인지 1인지를 확인
2. box의 값이 1인 경우, 해당 box의 방문 여부를 true로 설정함
3. 상하좌우의 box들을 따라 들어가, 2번과 같은 과정을 반복함

위 순서를 따르기 위해 가장 먼저 필요한 것은 해당 그래프를 순회하는 과정을 만드는 것이었습니다.

const [N, ...graph] = input;
const graphBoxes = graph.map((line) => line.split(""));
const countArray = [];
// 각 단지의 개수를 담아두기 위한 배열
const visited = {};
// 방문여부를 확인하기 위한 객체

graphBoxes.forEach((line, lineIndex) => {
  // 그래프의 각 라인마다 박스들을 확인함
  line.forEach((box, boxIndex) => {
    checkBox(lineIndex, boxIndex, box);
    // 각 박스마다 그 박스의 값과 방문여부를 확인하는 함수 생성 필요!
  });
});

// graphBoxes의 형태
[
  ["0", "1", "1", "0", "1", "0", "0"],
  ["0", "1", "1", "0", "1", "0", "1"],
  ["1", "1", "1", "0", "1", "0", "1"],
  ["0", "0", "0", "0", "1", "1", "1"],
  ["0", "1", "0", "0", "0", "0", "0"],
  ["0", "1", "1", "1", "1", "1", "0"],
  ["0", "1", "1", "1", "0", "0", "0"],
];

위 코드에서 보시다시피, 순회를 돌면서 각 위치(lineIndex, boxIndex)와 값(box)에 따라 처리를 해 줄 함수 checkBox가 필요했습니다. 이 함수는 각 박스의 순회 여부를 결정하고, 순회를 해야하는 경우 상하좌우를 DFS를 통해 순회하도록 설정해야 했습니다.

const getMarker = (y, x) => `${y},${x}`;
// visited 객체의 key값을 만들기 위해 필요한 함수

const checkBox = (lineIndex, boxIndex, box) => {
  // y(lineIndex), x(boxIndex), box 값을 받아옴
  if (box === "0") return;
  // box가 0인 경우 아파트가 없으므로 작업을 종료
  const marker = getMarker(lineIndex, boxIndex);
  // key값으로 사용될 marker 생성
  if (visited[marker]) return;
  // 이미 방문했을 경우 작업을 종료
  const queue = [marker];
  // 첫 값으로 만들어진 marker를 담은 queue 생성
  let curMarker;
  // 반복문을 돌면서 목표 지점이 될 marker
  let count = 0;
  // 해당 함수의 시작지점으로부터 얼마나 아파트를 돌았는지 확인하기 위한 변수

  while (queue.length) {
    curMarker = queue.pop();
    // 목표지점으로 사용될 marker를 설정
    const [y, x] = curMarker.split(",").map((value) => Number(value));
    // 몇 번째 줄, 몇 번째 box인지를 알아냄

    if (!visited[curMarker] && graphBoxes[y][x] === "1") {
      // 방문하지 않은 값이 "1"인 box들일 경우에만 작업을 진행함
      visited[curMarker] = true;
      // 방문을 하는 상황으로 설정
      count += 1;
      // 상하좌우를 돌면서 queue에 넣어줌
      if (y - 1 >= 0) queue.push(getMarker(y - 1, x));
      if (x - 1 >= 0) queue.push(getMarker(y, x - 1));
      if (y + 1 < N) queue.push(getMarker(y + 1, x));
      if (x + 1 < N) queue.push(getMarker(y, x + 1));
    }
  }

  if (count) countArray.push(count);
};

위 함수를 통해서 반복 작업 시 box가 방문하지 않은 ‘1’인 경우에만 그래프 순회를 통해 개수 세기를 진행하도록 할 수 있었습니다.

GITHUB  EMAIL