백준 js 1913번

 

<문제>

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

 

 

 

 

<문제 핵심>

1.  문제에서 필요한 능력은 구현문제 였고 주어진 숫자 N*N만큼 grid 격자를 만든다음 시작위치(0,0)부터 움직이면서 최종적으로 35가 어느 좌표에 있는지를 구하는 문제였다. grid격자를 만들고 난 후 표를 어떻게 채워야하는지 고민해봤고 일단 49를 0,0 좌표에 대입한 다음 시작하였다. 

 

2. 좌표 이동을 위해서 암묵적 그래프 dx, dy 배열을 만들었고 기본 방향을 하향으로 설정했다. 이후 이동하면서 이동방향을 변환하기 위해서 direction = (direction + 1) % 4를 적용했다.

 

let dx = [1, 0, -1, 0]; //하 우 상 좌 방향으로 움직일 거임
let dy = [0, 1, 0, -1];
let direction = 0;

 

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

1. 입력받은 다음 찾아야 하는 숫자, 숫자가 위치한 좌표를 담기위한 배열(findLocation), grid 격자를 생성한다. grid 격자 같은 경우 2차원 배열 기반으로 생성했다. 초기 좌표는 0,0에서 시작하고 암묵적 그래프와 기본 방향을 설정한다.

 

✅ 기본방향 direction = 0이라 가정하면 dx[0], dy[0]을 보면 알 수 있는데 dx[0]은 1이므로 방향이 밑으로 가는 것을 알 수 있다. 추후 dx[direction], dy[direction]을 적용할 때 이용된다.

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

const n = +input.shift();
const findLocationNumber = +input[0]; //35를 의미
const findLocation = [];
const grid = Array.from({ length: n }, () => Array(n).fill(0));

let endNumbers = n * n; //49
let [x, y] = [0, 0];

let dx = [1, 0, -1, 0]; //하 우 상 좌 방향으로 움직일 거임
let dy = [0, 1, 0, -1];
let direction = 0;

 

 

 

2.  0,0에 49를 대입한 다음 기본방향인 밑으로 이동하면서 새로운 좌표 nx, ny를 구한다. 새로운 좌표가 격자의 넓이를 벗어나지 않는지, 그리고 격자의 기본값이 0인지 아닌지를 판단하여 만약 조건에 벗어난다면 방향 전환을 실시한다. 이후 x,y를 갱신한 뒤 다시 반복문의 처음으로 돌아가는데 만약 findLocationNumber를 찾았다면 그떄의 x좌표, y좌표를 findLocation 배열에 넣는다. (출력할 때 초기 인덱스를 1로 생각하기 때문에 +1씩 더 해주고 푸쉬하기)

while (endNumbers > 0) {
  grid[x][y] = endNumbers;
  if (endNumbers === findLocationNumber) {
    findLocation.push(x + 1, y + 1); //2차원 배열
  }

  const nx = x + dx[direction];
  const ny = y + dy[direction];

  if (nx < 0 || ny < 0 || nx >= n || ny >= n || grid[nx][ny] !== 0) {
    direction = (direction + 1) % 4;
  }

  x += dx[direction];
  y += dy[direction];

  endNumbers--;
}

 

 

3.  격자의 한줄씩을 모두 출력하고 다음 줄에는 findLocation의 x좌표, y좌표를 구한다.

grid.map((x) => console.log(x.join(" ")));
console.log(findLocation[0], findLocation[1]);

 

 

<전체 코드>

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

const n = +input.shift();
const findLocationNumber = +input[0]; //35를 의미
const findLocation = [];
const grid = Array.from({ length: n }, () => Array(n).fill(0));

let endNumbers = n * n; //49
let [x, y] = [0, 0];

let dx = [1, 0, -1, 0]; //하 우 상 좌 방향으로 움직일 거임
let dy = [0, 1, 0, -1];
let direction = 0;

while (endNumbers > 0) {
  grid[x][y] = endNumbers;
  if (endNumbers === findLocationNumber) {
    findLocation.push(x + 1, y + 1); //2차원 배열
  }

  const nx = x + dx[direction];
  const ny = y + dy[direction];

  if (nx < 0 || ny < 0 || nx >= n || ny >= n || grid[nx][ny] !== 0) {
    direction = (direction + 1) % 4;
  }

  x += dx[direction];
  y += dy[direction];

  endNumbers--;
}

// 최종 결과 출력
grid.map((x) => console.log(x.join(" ")));
console.log(findLocation[0], findLocation[1]);