백준 2178 미로 찾기

문제

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

2178번: 미로 탐색

접근

1. DFS -> time over

2. BFS 

풀이

take-1: 실패 (10)

- [0,3] 큐를 마지막으로 반복문이 멈췄다. 

- idxPairs 까지는 뽑히는데 validPairs 에서 아무것도 검출되지 않았다. -> nx, ny 범위조건을 둘다 N 으로 해놨었다.

const solution = (input) => {
  const [N, M] = input.shift().split(" ").map(Number);
  const graph = [...input].map((v) => v.split("").map(Number));
  let answer = Number.MIN_SAFE_INTEGER;

  const inValidRange = (pair) => {
    const [nx, ny] = pair;
    if (nx < 0 || ny < 0 || nx >= N || ny >= N) return false;
    else if (graph[nx][ny] === 1) return true;
    return false;
  };

  const bfs = (row, col) => {
    const queue = [[row, col]];
    const seen = new Array(N).fill(0).map(() => new Array(N).fill(false));
    seen[row][col] = true;
    let cnt = 1;

    while (queue.length) {
      const [x, y] = queue.shift();
      graph[x][y] = 0;
      const idxPairs = [
        [x - 1, y],
        [x, y + 1],
        [x + 1, y],
        [x, y + 1],
      ];
      const validIdxPairs = idxPairs.filter((v) => inValidRange(v));

      for (let idxPair of validIdxPairs) {
        const [nx, ny] = idxPair;
        if (graph[nx][ny] === 1 && !seen[nx][ny]) {
          seen[nx][ny] = true;
          cnt++;
          console.log("nx,ny: ", nx, ny, "\n", "cnt: ", cnt, "queue: ", queue);
          queue.push([nx, ny]);
        }
      }
    }
    return cnt;
  };

  const count = bfs(0, 0);
  answer = answer < count ? count : answer;

  return answer;
};

console.log(solution(input));

take - 2: fail (17)

const solution = (input) => {
  const [N, M] = input.shift().split(" ").map(Number);
  const graph = [...input].map((v) => v.split("").map(Number));
  let answer = Number.MIN_SAFE_INTEGER;

  const inValidRange = (pair) => {
    const [nx, ny] = pair;
    if (nx < 0 || ny < 0 || nx >= N || ny >= M) return false;
    if (graph[nx][ny] === 1) return true;
    return false;
  };

  const bfs = (row, col) => {
    const queue = [[row, col]];
    const seen = new Array(N).fill(0).map(() => new Array(M).fill(false));
    seen[row][col] = true;
    let cnt = 1;

    while (queue.length) {
      const [x, y] = queue.shift();
      graph[x][y] = 0;
      const idxPairs = [
        [x - 1, y],
        [x, y - 1],
        [x + 1, y],
        [x, y + 1],
      ];

      const validIdxPairs = idxPairs.filter((v) => inValidRange(v));
      console.log(x, y);
      console.log(idxPairs);
      console.log(validIdxPairs);

      for (let idxPair of validIdxPairs) {
        const [nx, ny] = idxPair;
        if (graph[nx][ny] === 1 && !seen[nx][ny]) {
          seen[nx][ny] = true;
          cnt++;
          queue.push([nx, ny]);
        }
      }
      console.log("queue: ", queue);
    }
    return cnt;
  };

  const count = bfs(0, 0);
  answer = answer < count ? count : answer;
  return answer;
};

console.log(solution(input));

 

tial-3: success!!

const solution = (input) => {
  const [N, M] = input.shift().split(" ").map(Number);
  const graph = [...input].map((v) => v.split("").map(Number));
  let answer = Number.MIN_SAFE_INTEGER;

  const inValidRange = (pair) => {
    const [nx, ny] = pair;
    if (nx < 0 || ny < 0 || nx >= N || ny >= M) return false;
    if (graph[nx][ny] === 1) return true;
    return false;
  };

  const bfs = (row, col) => {
    const queue = [[row, col]];
    const seen = new Array(N).fill(0).map(() => new Array(M).fill(0));
    seen[row][col] = 1;

    while (queue.length) {
      const [x, y] = queue.shift();
      graph[x][y] = 0;
      const idxPairs = [
        [x - 1, y],
        [x, y - 1],
        [x + 1, y],
        [x, y + 1],
      ];

      const validIdxPairs = idxPairs.filter((v) => inValidRange(v));
      console.log(x, y);
      console.log(idxPairs);
      console.log(validIdxPairs);

      for (let idxPair of validIdxPairs) {
        const [nx, ny] = idxPair;
        if (graph[nx][ny] === 1 && !seen[nx][ny]) {
          seen[nx][ny] = seen[x][y] + 1;
          queue.push([nx, ny]);
        }
      }
      console.log("queue: ", queue);
    }
    return seen[N - 1][M - 1];
  };

  const count = bfs(0, 0);
  answer = answer < count ? count : answer;
  return answer;
};

console.log(solution(input));