[백준] 1347 미로 만들기 : 자바스크립트(node.js)

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

 

문제

홍준이는 미로 안의 한 칸에 남쪽을 보며 서있다. 미로는 직사각형 격자모양이고, 각 칸은 이동할 수 있거나, 벽을 포함하고 있다. 모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다. 홍준이는 미로에서 모든 행과 열의 이동할 수 있는 칸을 걸어다녔다. 그러면서 자신의 움직임을 모두 노트에 쓰기로 했다. 홍준이는 미로의 지도를 자기 노트만을 이용해서 그리려고 한다.

입력으로 홍준이가 적은 내용을 나타내는 문자열이 주어진다. 각 문자 하나는 한 번의 움직임을 말한다. ‘F’는 앞으로 한 칸 움직인 것이고, ‘L'과 ’R'은 방향을 왼쪽 또는 오른쪽으로 전환한 것이다. 즉, 90도를 회전하면서, 위치는 그대로인 것이다.

 

입력

첫째 줄에 홍준이가 적은 내용의 길이가 주어진다. 길이는 0보다 크고, 50보다 작다. 둘째 줄에 홍준이가 적은 내용이 내용이 주어진다.

19
FLFRFFRFFFRFFRFLFLL

 

출력

첫째 줄에 미로 지도를 출력한다. ‘.’은 이동할 수 있는 칸이고, ‘#’는 벽이다.

#..#
....
.##.
....

 

 

풀이 방법

 

문제 자체는 간단하다

주어진 입력에 따라 지도를 그리면 됨!

 

그렇지만 이 문제의 가장 큰 요점은 최종 배열의 크기를 모르고, 최종 배열에서 시작점의 좌표가 어디인지조차 모른다는 것이다

그래서 그냥 시작점을 0, 0의 좌표로 잡고 입력의 방향대로 움직이게 했다

그럼 얘가 회전할때는 방향을 바꿔주고, 전진할때는 전진한 새로운 좌표들을 넣은 배열을 만들었다

// 0 1 2 3 우 하 좌 상
const dx = [0, 1, 0, -1];
const dy = [1, 0, -1, 0];

let way = [];
  let cx = 0;
  let cy = 0;
  way.push([cx, cy]);
  let direc = 1; // 시작은 아래방향
  for (let i = 0; i < N; i++) {
    if (route.charAt(i) === "R") {
      direc = (direc + 1) % 4;
    } else if (route.charAt(i) === "L") {
      direc = (direc - 1) % 4;
      direc === -1 ? (direc = 3) : null;
    } else {
      cx += dx[direc];
      cy += dy[direc];
    }
    way.push([cx, cy]);
  }

 

사실 풀고 나서 생각한건데 

if (route.charAt(i) === "R") {
      direc = (direc + 1) % 4;
    } else if (route.charAt(i) === "L") {
      direc = (direc - 1) % 4;
      direc === -1 ? (direc = 3) : null;
    }

 

이 부분은 불필요한 코드가 들어가긴 했다..

어차피 증가하는거면 direc이 4가 됐을 때 0으로 바꿔주고, 감소하는거면 direc이 -1일 경우에 3으로만 바꿔주면 되는데

뭐 아무튼 

 

저 과정을 거치면 way라는 배열에 얘가 거친 모든 좌표들이 저장된다. 단 여기서 좌표는 시작점을 0, 0 으로 놓았기 때문에 음수의 좌표도 가질 수 있게 된다.

우리는 결국 얘가 움직인 경로를 그려야 하기 때문에 음수의 좌표는 계산할수가 없다

그리고 지금 하나 더 모르는건 최종 맵의 가로세로 길이도 모른다

 

이건 얘가 지금 거쳐온 경로 배열인 way를 돌면서 확인한다

x방향과 y방향 각각 좌표의 최대와 최소를 구하고, 최대 - 최소 + 1 하면 가로세로 길이를 구할 수 있다.

  let mxx = Number.MIN_SAFE_INTEGER;
  let mnx = Number.MAX_SAFE_INTEGER;
  let mxy = Number.MIN_SAFE_INTEGER;
  let mny = Number.MAX_SAFE_INTEGER;
  for (let i = 0; i <= N; i++) {
    mxx = Math.max(mxx, way[i][0]);
    mnx = Math.min(mnx, way[i][0]);
    mxy = Math.max(mxy, way[i][1]);
    mny = Math.min(mny, way[i][1]);
  }
  const xl = mxx - mnx + 1;
  const yl = mxy - mny + 1;

 

...코드가 더럽다

킵고잉

이제 최종 배열의 가로세로 크기를 알았으니 배열을 만들어주고

  let map = Array.from(Array(xl), () => Array(yl).fill("#"));

 

얘가 거쳐온 way의 좌표에 따라 "."을 심어주면 되는데

아까 말했듯 way의 좌표는 음수가 있으므로

모든 좌표에서 방금 위에서 구한 각 x방향과 y방향의 최솟값을 빼주면 음수가 아닌 좌표를 구할 수 있다

 

그러니까

x방향의 최소 좌표가 -4였다고 치면

최종 배열에서는 -4의 인덱스가 0이어야 하는 거니까

만약 내가 옮기고자 하는 x좌표가 -3이면 -3-(-4) = 1 해서 얘의 최종 x 좌표는 1인거다

  for (let i = 0; i <= N; i++) {
    map[way[i][0] - mnx][way[i][1] - mny] = ".";
  }

 

그 좌표에는 . 을 심어주고

저걸 출력하는 코드까지 전문 완성은 밑에 작성해두었다.

 

이렇게 풀면 시간초과도 안나고 맞았습니다!! 를 받을 수 있는데

다른 풀이를 참고한 결과 내가 간과한게 있었다

 

길이는 0보다 크고, 50보다 작다. 

그러니까 얘의 최종 배열의 크기는 그렇게 크지 않다

계속 앞으로만 전진한다고 가정해서 최대 배열을 구해봤자 가로세로 101인거다

그럼 굳이 좌표를 변환할 필요 없이 가로세로 101인 배열을 만들어서 중앙을 기준으로 움직였으면

더 간편하게 풀 수 있었을 것 같다....

 

뭐 아무튼 이러면서 배우는거지

 

내가 푼 최종 코드 ⬇️

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

const N = parseInt(input[0]);
const route = input.splice(1)[0];
// 0 1 2 3 우 하 좌 상
const dx = [0, 1, 0, -1];
const dy = [1, 0, -1, 0];

const solution = () => {
  let way = [];
  let cx = 0;
  let cy = 0;
  way.push([cx, cy]);
  let direc = 1; // 시작은 아래방향
  for (let i = 0; i < N; i++) {
    if (route.charAt(i) === "R") {
      direc = (direc + 1) % 4;
    } else if (route.charAt(i) === "L") {
      direc = (direc - 1) % 4;
      direc === -1 ? (direc = 3) : null;
    } else {
      cx += dx[direc];
      cy += dy[direc];
    }
    way.push([cx, cy]);
  }
  let mxx = Number.MIN_SAFE_INTEGER;
  let mnx = Number.MAX_SAFE_INTEGER;
  let mxy = Number.MIN_SAFE_INTEGER;
  let mny = Number.MAX_SAFE_INTEGER;
  for (let i = 0; i <= N; i++) {
    mxx = Math.max(mxx, way[i][0]);
    mnx = Math.min(mnx, way[i][0]);
    mxy = Math.max(mxy, way[i][1]);
    mny = Math.min(mny, way[i][1]);
  }
  const xl = mxx - mnx + 1;
  const yl = mxy - mny + 1;

  let map = Array.from(Array(xl), () => Array(yl).fill("#"));
  let answer = "";
  for (let i = 0; i <= N; i++) {
    map[way[i][0] - mnx][way[i][1] - mny] = ".";
  }
  for (let i = 0; i < xl; i++) {
    for (let j = 0; j < yl; j++) {
      answer += map[i][j];
    }
    answer += "\n";
  }
  console.log(answer);
};

solution();