백준 5547번

QUESTION LINK

집을 감싸는 부분의 길이와 내부의 비어있는 곳의 길이를 각각 BFS로 구해야하는 문제였습니다. 풀이의 순서는 아래와 같습니다.

1. 인접한 집들의 길이의 합 구하기 (내부에 빈 공간과 접한 곳의 길이도 포함)
2. 인접한 집들의 길이의 합 구할 때 비어있는 공간들의 좌표 구하기
3. 빈 공간 좌표들을 통해 빈 공간들 중 집 내부에 속하는 부분들의 길이 구하기
4. 인접한 집들의 길이 합 - 집 내부에 속하는 부분들의 길이

처음에 1, 2번의 계산 과정을 진행하기 위해, 기존 BFS를 적용하던 방식대로 BFS를 통해 길이들을 구해주고자 했습니다. 이 때, 육각형의 집이기 때문에 BFS를 하면서 총 6군데의 인접한 곳들을 확인하고 넘어가는 방식으로 진행했습니다. 그리고, 집과 빈 공간(좌표를 갖고 있는)이 만나는 지점에 대해서 길이를 1씩 추가하도록 했습니다.

const [numbers, ...graph] = input;
const [W, H] = numbers.split(" ").map((v) => +v);
// W는 너비, H는 높이
const graphBoxes = graph.map((line) => line.split(" "));
// 그래프 변수
const visitedWhenLines = {}; // check houses
// 집의 둘레를 구할 때 방문 여부를 확인하기 위한 객체
const visitedWhenEmtpy = new Set();
// 빈 곳들 중 집 내부에 속한 곳을 구할 때 방문 여부를 확인하기 위한 Set
const aroundChangesWithZero = [
  [-1, 0],
  [-1, 1],
  [0, -1],
  [0, 1],
  [1, 0],
  [1, 1],
]; // 줄의 index가 짝수인 경우에 대한 주변 변경 좌표들
const aroundChangesWithOne = [
  [-1, -1],
  [-1, 0],
  [0, -1],
  [0, 1],
  [1, -1],
  [1, 0],
]; // 줄의 index가 홀수인 경우에 대한 주변 환경 좌표들

const getMarker = (y, x) => `${y},${x}`;
// visited에 key값으로서 활용하기 위한 마커 생성

const queueWhenLines = [];
// 집 둘레를 구할 때 사용할 queue
const firstMarker = getMarker(0, 0);
// 초기 값은 좌표(0,0)으로 설정
visitedWhenLines[firstMarker] = true;
queueWhenLines.push(firstMarker);
// queue에 초기값을 담아줌
if (graphBoxes[0][0] === "0") visitedWhenEmtpy.add(firstMarker);
// 방문한 곳이 비어있는 곳일 때, 추후 집 내부를 확인 시 사용할 visited Set에 마커를 담아줌

let curHouse;
let curIndex = 0;
let totalLines = 0;
let emptyLines = 0;

// while 문을 돌면서 queue 내에 있는 것들을 확인해 BFS를 진행함
while (queueWhenLines[curIndex]) {
  curHouse = queueWhenLines[curIndex];
  curIndex += 1;

  const [y, x] = curHouse.split(",").map((v) => +v);
  const aroundChanges = y % 2 ? aroundChangesWithOne : aroundChangesWithZero;
  // 높이가 짝수, 홀수인 경우에 다른 방향값을 가져옴
  const curValue = graphBoxes[y][x];

  aroundChanges.forEach(([dy, dx]) => {
    // 각각의 방향값에 따른 처리 진행
    const aroundY = y + dy;
    const aroundX = x + dx;

    if (aroundY < 0 || aroundY >= H || aroundX < 0 || aroundX >= W) {
      // 값이 존재하지 않는 경우 집이 외부와 닿는 것이므로 길이를 1추가
      if (curValue === "1") totalLines += 1;
      return;
    }

    const aroundValue = graphBoxes[aroundY][aroundX];
    if (curValue === "1" && aroundValue === "0") totalLines += 1;
    // 집이 빈 곳과 맞닿는 경우 길이 1추가

    const aroundMarker = getMarker(aroundY, aroundX);
    if (!visitedWhenLines[aroundMarker]) {
      // 방문하지 않은 곳에 대해서만 queue를 넣어 처리 진행
      if (aroundValue === "0") visitedWhenEmtpy.add(aroundMarker);
      // 빈 곳에 대한 추후 처리를 위해 visited Set에 추가
      visitedWhenLines[aroundMarker] = true;
      // 방문했음을 표기하고 queue에 추가
      queueWhenLines.push(aroundMarker);
    }
  });
}

위 코드를 통해, 아래와 같은 Set 값을 얻을 수 있게 됩니다.

Set(14) {
  '0,0',
  '1,0',
  '0,2',
  '2,1',
  '1,3',
  '3,0',
  '0,4',
  '1,4',
  '2,3',
  '3,3',
  '1,6',
  '3,5',
  '1,7',
  '3,7'
}

이 Set값을 통해 다음으로 진행할 것은 집 내부에 속한 곳을 찾아내는 것입니다. 이 부분에서 계산의 순서는 아래와 같습니다.

1. 구해진 Set을 순회하며 빈 곳들과 연결된 다른 빈 곳들을 따라 들어가는 BFS를 만듬
2. 빈 곳과 연결된 좌표에 집이 있을 시 길이를 1씩 늘림
3. 빈 곳과 연결된 좌표가 비어있을 시(외부인 경우) 해당 빈 곳으로부터 시작한 BFS의 모든 길이값은 무효화함
4. 무효화되지 않은 길이들의 총합을 구함

이 때, 순회를 돌면서 방문한 곳들은 다음 순회 시 방문할 필요가 없기 때문에 Set에서 delete하는 작업을 해줍니다. 이를 위해서 Set이라는 자료 구조를 사용했습니다.

// 빈 곳들의 모임으로부터 순회를 시작함
visitedWhenEmtpy.forEach((marker) => {
  const queue = [];
  const visited = {};
  let index = 0;
  let house;
  let line = 0;
  visited[marker] = true;
  queue.push(marker);

  // queue 순회를 돌면서 연결된 곳들을 계속 탐색함
  while (queue[index]) {
    house = queue[index];
    index += 1;

    const [y, x] = house.split(",").map((v) => +v);
    const aroundChanges = y % 2 ? aroundChangesWithOne : aroundChangesWithZero;
    // 주변의 요소들의 값들을 확인함
    aroundChanges.forEach(([dy, dx]) => {
      const aroundY = y + dy;
      const aroundX = x + dx;
      // 주변 요소가 외부일 경우, 해당 BFS는 집 내부에 속한 것이 아니므로 line값을 무효화함
      if (aroundY < 0 || aroundY >= H || aroundX < 0 || aroundX >= W) {
        line = undefined;
        return;
      }

      const aroundValue = graphBoxes[aroundY][aroundX];
      // 주변 요소가 같은 비어있는 곳일 경우, Set에서는 해당 값을 순회할 필요가 없으므로 지워주고, queue에 담아줌
      if (aroundValue === "0") {
        const aroundMarker = getMarker(aroundY, aroundX);
        if (!visited[aroundMarker]) {
          visitedWhenEmtpy.delete(aroundMarker);
          visited[aroundMarker] = true;
          queue.push(aroundMarker);
        }
      }
      // 주변에 집이 있는 경우, line값을 증가함
      if (aroundValue === "1") line += 1;
    });
  }

  // 모든 line값들을 더함
  if (line >= 0) emptyLines += line;
});

// 기존의 집 주변 값에서 내부 값을 빼어 결과를 구함
const result = totalLines - emptyLines;

위와 같은 과정을 진행하면서, 가장 큰 어려움을 느꼈던 부분은 순회를 두 번 돌아야 하는 지에 대한 판단을 제대로 하지 못한 것이었습니다. 처음에 집 주변 값(totalLines)을 구하는 것에는 문제가 없었으나, 집 내부의 빈 곳의 길이(emptyLines)를 구하는 것에서는 다시 한 번 순회를 돌아야하는 지에 대해 판단하지 못했는데, 미리 빈 곳들의 좌표를 구해놓고, 이를 Set을 통해 최소한 돌도록 처리해주는 부분이 이번 알고리즘에서 가장 빠르게 문제를 해결하는 데에 도움을 주었던 요소였습니다.

그리고, 문제를 풀며 마지막에 계속해서 해결하지 못했던 한 부분이 있었는데, 이는 아래 코드와 같이 초기 BFS 설정을 할 때, 제대로 queue에 값을 배치해주지 못하는 사소한 부분에서의 문제였습니다. 이러한 실수를 줄이기 위해 미리 확실한 변수를 설정하고 배열에 push의 형태로 대입해주는 것이 안전하다는 것을 느꼈습니다.

const visited = {};
let index = 0;
let house;
let line = 0;
visited[marker] = true;
const queue = [house];
// queue에 marker의 형태로 값이 들어와야 하는데 잘못된 값을 넣어서
// 초기에 undefined를 갖고 처리를 진행하는 문제가 발생함

GITHUB  EMAIL