백준 js 17129번

Jay_Jung 2024. 8. 13. 12:44

<문제>

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

<문제 핵심>

1. 지도에서 시작점이 2인걸(세 식구가 있는 위치) 기준으로 bfs 알고리즘을 통해 3, 4, 5에 해당하는 칸에 도달하는 최단거리를 구하는 문제였다. 이때 tak이라는 문구와 distance에 +1을 해주면서 3 , 4 또는 5에 도착했을 때 누적된 거리를 출력한다. 해당 문제의 경우 3에 도착했을 때 거리는 3이 될 것이다. 목표지점에 도달하지 못하는 경우에는 NIE를 출력한다.

-> 예제 입력이 다음과 같은 경우 시작점인 2를 기준으로 3과 4에 도달했을 때의 거리가 3이고 이때가 최단거리이다.

-> 해당 입력값일 경우 2를 기준으로 사방이 1로 막혀있으므로 3, 4, 5에 접근이 불가능하다. 이때는 NIE가 출력될 것이다.

2. 상하좌우로 이동하기 위한 암묵적 그래프를 생성한다.(dir 배열)

<문제 풀이과정 및 순서도>

1. 입력 받은 뒤 지도 배열을 생성하고 방문여부를 판단하기 위한 vistied 배열을 생성한다.

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n");

const [n, m] = input.shift().split(" ").map(Number);

const maps = input.map((line) => line.split("").map(Number));
console.log(maps);
const visited = Array.from({ length: n }, () => Array(m).fill(false));

2. maps배열에서 시작점인 2를 반복문을 통해 찾은다음 해당 좌표를 기준으로 bfs함수를 호출한다.

for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    if (maps[i][j] === 2) {
      bfs(i, j);
      return;
    }
  }
}

3. bfs함수 로직을 구현한다.

✅ 시작점일 때(2) 거리는 0이므로 queue에 distance 부분은 0으로 설정해준다.

✅ 상하좌우로 이동했을 때 좌표를 구한다음 미로의 범위를 벗어나는지 판단하고 방문처리 여부와 장애물이 없는지를 판단한다.

✅ 목표지점인 3, 4, 5에 도달했을 때 distance는 1개씩 증가하게 되고 이때 최단거리로 먹을 수 있는 음식을 찾을 수 있다. 입력값이 문제 핵심에서 서술한거와 같다면 3에 도달했을 때 distance는 3이므로 최단거리로 3이 출력될 것이다.

const bfs = (startX, startY) => {
  const queue = [[startX, startY, 0]];
  visited[startX][startY] = true;
  const dir = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];

  while (queue.length) {
    const [x, y, distance] = queue.shift();

    for (let [dx, dy] of dir) {
      const newX = x + dx;
      const newY = y + dy;

      // 범위 내에 있고, 아직 방문하지 않은 곳이어야 함
      if (newX >= 0 && newX < n && newY >= 0 && newY < m) {
        if (!visited[newX][newY] && maps[newX][newY] !== 1) {
          visited[newX][newY] = true;
          // 목표 지점(3, 4, 5)에 도달한 경우
          if (maps[newX][newY] >= 3 && maps[newX][newY] <= 5) {
            console.log("TAK");
            console.log(distance + 1);
            return;
          }
          // 빈 공간(0)인 경우 탐색 계속 진행
          if (maps[newX][newY] === 0) {
            queue.push([newX, newY, distance + 1]);
          }
        }
      }
    }
  }

  // 목표 지점에 도달하지 못한 경우
  console.log("NIE");
};

<전체 코드>

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n");

const [n, m] = input.shift().split(" ").map(Number);

const maps = input.map((line) => line.split("").map(Number));
console.log(maps);
const visited = Array.from({ length: n }, () => Array(m).fill(false));

const bfs = (startX, startY) => {
  const queue = [[startX, startY, 0]];
  visited[startX][startY] = true;
  const dir = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];

  while (queue.length) {
    const [x, y, distance] = queue.shift();

    for (let [dx, dy] of dir) {
      const newX = x + dx;
      const newY = y + dy;

      // 범위 내에 있고, 아직 방문하지 않은 곳이어야 함
      if (newX >= 0 && newX < n && newY >= 0 && newY < m) {
        if (!visited[newX][newY] && maps[newX][newY] !== 1) {
          visited[newX][newY] = true;
          // 목표 지점(3, 4, 5)에 도달한 경우
          if (maps[newX][newY] >= 3 && maps[newX][newY] <= 5) {
            console.log("TAK");
            console.log(distance + 1); //최단거리를 찾았다면 return 해주는거네
            return;
          }
          // 빈 공간(0)인 경우 탐색 계속 진행
          if (maps[newX][newY] === 0) {
            queue.push([newX, newY, distance + 1]);
          }
        }
      }
    }
  }

  // 목표 지점에 도달하지 못한 경우
  console.log("NIE");
};

for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    if (maps[i][j] === 2) {
      bfs(i, j);
      return;
    }
  }
}