백준23747 - 와드 (BFS) node.js

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

문제는 지도의 크기, 알파벳으로 이루어진 영역, 시작 위치, 한별이가 실행하는 행동이 주어질 때, 한별이의 시야를 출력한다.

 

문제 해결 방식

문제 해결을 위한 접근으로 세 가지를 구분하여 접근했다.

1. 'LRUD'와 같이 한별이의 움직임에 관한 입력이 주어졌을 시 현재 위치를 변동시키는 로직 구현.

2. 'W' 입력인 와드 설치가 주어졌을 시 현재 위치의 영역(알파벳)의 시야를 밝히는 BFS 로직 구현.

3. 마지막으로는 한별이의 마지막 위치에서의 상하좌우 시야 밝히기 구현.

 

소스 코드가 길다보니, 주석으로 설명을 대체한다.

 

변수 선언

4 5  // Y, X 지도 크기
aaabc // matrix 영역
dcbbc
dccaa
ddaaa
3 4  // location 현재 위치
WLLLWUURRD // queue 행동 대기열

 

전체 소스 코드

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

function solution(data) {
	// 변수 선언
  const [Y, X] = data.shift().split(" ").map(Number);
  const queue = data.pop().split("");
  let queueIdx = 0;
  let location = data
    .pop()
    .split(" ")
    .map((el) => +el - 1);
  const matrix = data.map((el) => el.split(""));
  const visions = Array.from({ length: Y }, () => {
    return Array.from({ length: X }, () => "#");
  });

	// 각 이동 명령어에 따른 위치 변화 반환 객체 함수
  const move = {
    L: (y, x) => [y, x - 1],
    R: (y, x) => [y, x + 1],
    U: (y, x) => [y - 1, x],
    D: (y, x) => [y + 1, x],
  };

	// 상하좌우 이동 좌표를 담은 배열
  const directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];
  
	// 유효한 위치인지 검증하는 함수
  const verify = (x, y) => X > x && x >= 0 && Y > y && y >= 0;

	// 'W' 입력 시 실행되는 함수 (영역 시야 밝히기)
  function BFS(x, y) {
    const t = matrix[y][x]; // 영역 (알파벳)
    const queue = [[x, y]]; // 시작 위치
    let queueIdx = 0;

    while (queueIdx < queue.length) {
      const [x, y] = queue[queueIdx++];
	
	// 이미 밝힌 시야라면 패스
      if (visions[y][x] === ".") continue;
      visions[y][x] = ".";

      directions.forEach(([dx, dy]) => {
        const [nx, ny] = [dx + x, dy + y];
		// 좌표 검증 & 암흑 시야 검증 & 영역 검증 후 대기열 추가
        if (verify(nx, ny) && visions[ny][nx] === "#" && matrix[ny][nx] === t) {
          queue.push([nx, ny]);
        }
      });
    }
  }

  while (queueIdx < queue.length) {
    const act = queue[queueIdx++];
    const [y, x] = location;
    // 명령어에 따른 라우팅
    if (act === "W") BFS(x, y);
    else location = move[act](y, x);
  }

	// 마지막 한별이의 위치에서 상하좌우 시야 밝히기
  const [ly, lx] = location;
  visions[ly][lx] = ".";
  directions.forEach(([dx, dy]) => {
    const [nx, ny] = [dx + lx, dy + ly];
    if (verify(nx, ny)) visions[ny][nx] = ".";
  });

  console.log(visions.map((el) => el.join("")).join("\n"));
}

solution(input);