백준 14940번

QUESTION LINK

그래프 순회를 하여 기준점으로부터의 거리값을 구하는 문제였습니다. 이 문제의 경우, BFS를 통해 한 점으로 부터 사방으로 이동할 때마다 이동거리를 한 칸 넓히는 방식을 통해 각 칸에서의 길이를 구하면 되었습니다.

잘못된 풀이 : 각 점으로 부터 ‘2’까지의 거리 구하기

하지만, 초반에 잘못된 방법으로 풀고자 하여, 기준점을 “2”에 두는 것이 아닌, 모든 각각의 점에 대해 기준점을 두고 2까지 가는 데에 필요한 길이를 구하는 방식으로 진행을 하여, 아래와 같은 코드가 나왔고, 이로 인해 ‘시간 초과’가 계속해서 나오는 문제가 있었습니다.

const [numbers, ...graph] = input;
const [n, m] = numbers.split(" ");
const N = Number(n);
const M = Number(m);
const graphBoxes = graph.map((line) => line.split(" "));
const resultArray = [...Array(N)].map(() => [...Array(M)]);
// 결과를 담을 배열

const getMarker = (y, x) => `${y},${x}`;
const getQueueItem = (y, x, floor) => `${getMarker(y, x)},${floor}`;

const checkBox = (lineIndex, boxIndex, box) => {
  if (box === "0") {
    // 0일 때 그 위치의 값은 0으로 설정
    resultArray[lineIndex][boxIndex] = "0";
    return;
  }
  if (box === "2") {
    // 2일 때 그 위치의 값은 0으로 설정
    resultArray[lineIndex][boxIndex] = "0";
    return;
  }

  const visited = {};
  // 방문여부를 확인하는 객체
  const queue = [getQueueItem(lineIndex, boxIndex, 0)];
  // 최초 값은 함수를 통해 들어온 위치
  let curItem;

  while (queue.length) {
    curItem = queue.shift();
    const [y, x, floor] = curItem.split(",").map((value) => Number(value));
    // 해당 박스의 좌표와 몇 번을 거쳐 왔는지 나타내는 floor 값
    const curMarker = getMarker(y, x);
    const curValue = graphBoxes[y][x];

    if (!visited[curMarker] && curValue === "2") {
      // 2인 경우 추가적인 queue를 넣지 않고 거쳐온 정도를 넣어준 뒤 종료
      visited[curMarker] = true;
      resultArray[lineIndex][boxIndex] = floor;
    }

    if (!visited[curMarker] && curValue === "1") {
      // 1인 경우 주변 요소도 확인하도록 queue에 push
      visited[curMarker] = true;

      if (y - 1 >= 0) queue.push(getQueueItem(y - 1, x, floor + 1));
      if (x - 1 >= 0) queue.push(getQueueItem(y, x - 1, floor + 1));
      if (y + 1 < N) queue.push(getQueueItem(y + 1, x, floor + 1));
      if (x + 1 < M) queue.push(getQueueItem(y, x + 1, floor + 1));
    }
  }
};

// 문제가 되었던 곳. 모든 값을 돌아 길이를 구하려 해서 시간이 늘어남
graphBoxes.forEach((line, lineIndex) => {
  line.forEach((box, boxIndex) => {
    checkBox(lineIndex, boxIndex, box);
  });
});

const result = resultArray.map((line) => line.join(" ")).join("\n");

console.log(result);

위 코드로 작성해, 모든 값에 대한 길이를 구하다보니 시간이 늘어나게 되어 이를 해결하기 위한 다른 방법을 찾게 되었습니다.

‘2’를 시작점으로 설정하고 주변 길이 구하기

여러번의 BFS 순회를 하는 것이 아니라, 한 번의 BFS만을 통해 모든 위치의 값을 구하면 된다는 것을 알게 되었고, 이를 적용하고자 했습니다. 이 때, 문제의 사항 중 고려하지 못했던 부분이 하나 더 있었는데, ‘1’로 된 곳 중, 방문을 아예 하지 못한 곳은 ‘-1’로 처리한다는 것입니다. 처음에는 이 사항에 대한 고려가 없어 계속 틀렸다는 결과가 나왔는데, 문제를 다시 파악해보니 이와 같은 조건이 같이 있었다는 것을 알았습니다. 문제를 꼼꼼하게 읽는 것이 풀이보다 더 중요하다는 걸 느끼는 순간이었습니다…

const input = fs.readFileSync(filePath).toString().trim().split("\n");
const [numbers, ...graph] = input;
const [n, m] = numbers.split(" ");
const N = Number(n);
const M = Number(m);
const graphBoxes = graph.map((line) => line.split(" "));
const destination = [];

// '2'의 위치를 처음에 파악해 저장해둠
graphBoxes.forEach((line, lineIndex) => {
  line.forEach((box, boxIndex) => {
    if (box === "2") destination.push(lineIndex, boxIndex);
  });
});

const getMarker = (y, x) => `${y},${x}`;
const getQueueItem = (y, x, floor) => `${getMarker(y, x)},${floor}`;
// floor 값은 BFS로 탐색을 들어간 횟수를 나타냄

const BFS = () => {
  const [destY, destX] = destination;
  // '2'의 위치
  const visited = {};
  // 방문한 곳을 나타내는 객체
  const queue = [getQueueItem(destY, destX, 0)];
  // 최초값으로 '2'의 위치를 넣어줌. 2는 어느 곳에 대한 이동도 없으므로 floor값은 0
  let curItem;

  while (queue.length) {
    curItem = queue.shift();
    const [y, x, floor] = curItem.split(",").map((value) => Number(value));
    // 방문한 곳의 좌표, 탐색 횟수
    const curMarker = getMarker(y, x);
    const curValue = graphBoxes[y][x];

    if (curValue === "0") {
      // 값이 0인 경우 0으로 설정
      graphBoxes[y][x] = 0;
    }

    if (!visited[curMarker] && (curValue === "1" || curValue === "2")) {
      // 값이 1, 2인 경우 해당 위치를 방문했음을 표기하고 주변 위치를 탐색
      visited[curMarker] = true;
      graphBoxes[y][x] = floor;
      if (y - 1 >= 0) queue.push(getQueueItem(y - 1, x, floor + 1));
      if (x - 1 >= 0) queue.push(getQueueItem(y, x - 1, floor + 1));
      if (y + 1 < N) queue.push(getQueueItem(y + 1, x, floor + 1));
      if (x + 1 < M) queue.push(getQueueItem(y, x + 1, floor + 1));
    }
  }
};

BFS();

// 0인 경우, -1인 경우를 표기함
graphBoxes.forEach((line) => {
  line.forEach((box, boxIndex) => {
    if (box === "0") line[boxIndex] = 0;
    if (box === "1") line[boxIndex] = -1;
  });
});

const result = graphBoxes.map((line) => line.join(" ")).join("\n");

console.log(result);

이번 문제를 풀면서 난이도가 쉬운 문제도 문제에 대한 해결 방향을 잘못 잡거나, 문제를 잘못 읽은 경우 문제 풀이에 큰 문제가 생길 수 있음을 다시 느낄 수 있었습니다! 문제 해결에 앞서서 문제 이해 및 풀이를 위한 설계를 조금 더 신경쓰기로 했습니다.

🔎 현재 코드의 경우, 상당히 긴 시간과 메모리를 소모하며 문제를 해결하게 됩니다. 추후 다시 문제를 풀면서 해당 부분에 대한 해결도 필요합니다.

GITHUB  EMAIL