문제
풀이
요구사항
N*M크기의 맵이 있고, 출발지의 위치와 목적지의 위치가 주어졌을 때, A*B 크기의 유닛이 목적지 까지 도달하는 데에 필요한 최소 이동 수를 출력하라.
유닛이 이동하는 경로에 장애물이 한 칸이라도 걸쳐 있을 경우 유닛은 해당 방향으로 이동하지 못한다.
해결방안
방법 1
네 방향을 확인하며 BFS를 수행한다.
지도의 크기(500*500) 네 방향(4) 유닛의 너비 or 높이(10) = 10,000,000 이기 때문에 시간초과는 나지 않는다.
이때 유닛이 장애물에 조금이라도 걸쳐지면 해당 방향으로는 이동하지 못하기 때문에 이동하기 전에 이동하는 방향의 변이 모두 이동할 수 있는지 확인해줘야 한다.
유닛의 좌표는 유닛의 가장 왼쪽, 가장 윗칸을 기준으로 설정된다. 따라서 유닛의 가장 왼쪽, 가장 윗칸의 좌표를 (y,x)라고 해보겠다.
한 방향으로 이동할 때 우리가 확인해줘야 할 건 세 가지다.
- 이동했을 때 범위를 벗어나는가?
- 이미 방문했던 적이 있는 곳인가?
- 장애물이 있는가?
먼저 코드부터 확인해보자.
for (let i = 0; i < 4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
if (!outOfRange(ny, nx) && !visited[ny][nx] && availiable(ny, nx, i)) {
visited[ny][nx] = true;
queue.enqueue([ny, nx, move + 1]);
}
}우선 첫 번째, 이동했을 때 범위를 벗어나는지 확인하는 함수인 outOfRange함수는 아래와 같다.
function outOfRange(y, x) {
return y < 0 || x < 0 || y + A > N || x + B > M;
}범위를 벗어난다면 true, 벗어나지 않는다면 false를 반환한다.
두 번째, 이미 방문했던 적이 있는지는 visited변수를 통해 확인한다.
세 번째, 장애물이 있는지 확인한다.
위쪽 방향으로 이동하는 과정을 예시를 들자면, 아래와 같이 순서도를 작성할 수 있다.
- (y-1,x)를 확인해서 장애물이 있는지 확인한다.
1-1. 만약 장애물이 없다면 x를 1 증가시킨다.
1-2. 장애물이 있다면 해당 방향으로 이동할 수 없으므로 현재 방향의 탐색을 종료한다. - x가 x+B보다 작다면 위 과정을 반복한다.
이를 네가지 방향에 모두 고려하여 코드로 구현해보면 아래와 같다.
function availiable(y, x, d) {
// 상
if (d === 0) {
for (let i = 0; i < B; i++) {
if (map[y][x + i]) return false;
}
}
// 하
else if (d === 1) {
for (let i = 0; i < B; i++) {
if (map[y + A - 1][x + i]) return false;
}
}
// 좌
else if (d === 2) {
for (let i = 0; i < A; i++) {
if (map[y + i][x]) return false;
}
}
// 우
else {
for (let i = 0; i < A; i++) {
if (map[y + i][x + B - 1]) return false;
}
}
return true;
}전체 코드는 아래와 같다.
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M, A, B, K] = input[0].split(' ').map(Number);
const obstacles = input.slice(1, 1 + K).map((e) => e.split(' ').map(Number));
const start = input[1 + K].split(' ').map((e) => Number(e) - 1);
const end = input[2 + K].split(' ').map((e) => Number(e) - 1);
const map = Array.from({ length: N }, () => Array(M).fill(0));
const visited = Array.from({ length: N }, () => Array(M).fill(false));
// 장애물 설정
for (let [y, x] of obstacles) {
map[y - 1][x - 1] = 1;
}
const dy = [-1, 1, 0, 0];
const dx = [0, 0, -1, 1];
class Queue {
constructor() {
this.queue = {};
this.front = 0;
this.rear = 0;
}
enqueue(value) {
this.queue[this.rear++] = value;
}
dequeue() {
const temp = this.queue[this.front];
delete this.queue[this.front];
this.front++;
if (this.rear === this.front) {
this.rear = this.front = 0;
}
return temp;
}
size() {
return this.rear - this.front;
}
}
function bfs() {
const queue = new Queue();
queue.enqueue([...start, 0]);
while (queue.size() > 0) {
let [y, x, move] = queue.dequeue();
// 목적지에 도달했다면
if (y === end[0] && x === end[1]) return move;
for (let i = 0; i < 4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
if (!outOfRange(ny, nx) && !visited[ny][nx] && availiable(ny, nx, i)) {
visited[ny][nx] = true;
queue.enqueue([ny, nx, move + 1]);
}
}
}
return -1;
}
function availiable(y, x, d) {
// 상
if (d === 0) {
for (let i = 0; i < B; i++) {
if (map[y][x + i]) return false;
}
}
// 하
else if (d === 1) {
for (let i = 0; i < B; i++) {
if (map[y + A - 1][x + i]) return false;
}
}
// 좌
else if (d === 2) {
for (let i = 0; i < A; i++) {
if (map[y + i][x]) return false;
}
}
// 우
else {
for (let i = 0; i < A; i++) {
if (map[y + i][x + B - 1]) return false;
}
}
return true;
}
function outOfRange(y, x) {
return y < 0 || x < 0 || y + A > N || x + B > M;
}
let answer = bfs();
console.log(answer);
방법 2
1번 방법은 availiable 함수에서 방향에 따라 동작이 조금씩 달라지기 때문에 이를 if문으로 취사선택 해주도록 작성했다.
그러다보니 중복되는 부분이 많아지고 코드가 길어져서 보기가 좋지 않았다.
그래서 다른 분들의 코드를 봤는데, 이렇게 하는 방법도 있구나 싶은게 있어서 이 방법도 추가로 설명해보고자 한다.
달라진 availiable 함수는 아래와 같다.
function availiable(y, x) {
for (let i = 0; i < A; i++) {
for (let j = 0; j < B; j++) {
if (map[y + i][x + j]) return false;
}
}
return true;
}방법 1에서 작성한 available함수는 현재 가는 방향의 모서리 변만 확인해주도록 코드를 작성했었는데, 이 방법은 유닛의 전체를 확인하는 방법이 사용된다.
이렇게 하면 시간 복잡도는 지도의 크기(500*500) 네 방향(4) 유닛의 크기(10*10) = 100,000,000 이 된다.
시간은 늘었지만 시간 제한이 2초이기 때문에 통과할 수 있다.
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M, A, B, K] = input[0].split(' ').map(Number);
const obstacles = input.slice(1, 1 + K).map((e) => e.split(' ').map(Number));
const start = input[1 + K].split(' ').map((e) => Number(e) - 1);
const end = input[2 + K].split(' ').map((e) => Number(e) - 1);
const map = Array.from({ length: N }, () => Array(M).fill(0));
const visited = Array.from({ length: N }, () => Array(M).fill(false));
// 장애물 설정
for (let [y, x] of obstacles) {
map[y - 1][x - 1] = 1;
}
const dy = [-1, 1, 0, 0];
const dx = [0, 0, -1, 1];
function bfs() {
const queue = [[...start, 0]];
let front = 0;
while (queue.length > front) {
let [y, x, move] = queue[front++];
// 목적지에 도달했다면
if (y === end[0] && x === end[1]) return move;
for (let i = 0; i < 4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
if (!outOfRange(ny, nx) && !visited[ny][nx] && availiable(ny, nx)) {
visited[ny][nx] = true;
queue.push([ny, nx, move + 1]);
}
}
}
return -1;
}
function availiable(y, x) {
for (let i = 0; i < A; i++) {
for (let j = 0; j < B; j++) {
if (map[y + i][x + j]) return false;
}
}
return true;
}
function outOfRange(y, x) {
return y < 0 || x < 0 || y + A > N || x + B > M;
}
let answer = bfs();
console.log(answer);추가로 기존에 있던 Queue를 지우고, 배열을 queue처럼 사용하도록 변경했다.
이렇게 하면 메모리는 더 사용하는 대신 시간이 줄어든다는 장점이 있다.
최종코드
최종 코드는 방법 1에서 사용된 available함수의 형태를 채택하고, Queue 대신 배열을 사용하는 방법으로 했다.
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M, A, B, K] = input[0].split(' ').map(Number);
const obstacles = input.slice(1, 1 + K).map((e) => e.split(' ').map(Number));
const start = input[1 + K].split(' ').map((e) => Number(e) - 1);
const end = input[2 + K].split(' ').map((e) => Number(e) - 1);
const map = Array.from({ length: N }, () => Array(M).fill(0));
const visited = Array.from({ length: N }, () => Array(M).fill(false));
// 장애물 설정
for (let [y, x] of obstacles) {
map[y - 1][x - 1] = 1;
}
const dy = [-1, 1, 0, 0];
const dx = [0, 0, -1, 1];
function bfs() {
const queue = [[...start, 0]];
let front = 0;
while (queue.length > front) {
let [y, x, move] = queue[front++];
// 목적지에 도달했다면
if (y === end[0] && x === end[1]) return move;
for (let i = 0; i < 4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
if (!outOfRange(ny, nx) && !visited[ny][nx] && availiable(ny, nx, i)) {
visited[ny][nx] = true;
queue.push([ny, nx, move + 1]);
}
}
}
return -1;
}
function availiable(y, x, d) {
// 상
if (d === 0) {
for (let i = 0; i < B; i++) {
if (map[y][x + i]) return false;
}
}
// 하
else if (d === 1) {
for (let i = 0; i < B; i++) {
if (map[y + A - 1][x + i]) return false;
}
}
// 좌
else if (d === 2) {
for (let i = 0; i < A; i++) {
if (map[y + i][x]) return false;
}
}
// 우
else {
for (let i = 0; i < A; i++) {
if (map[y + i][x + B - 1]) return false;
}
}
return true;
}
function outOfRange(y, x) {
return y < 0 || x < 0 || y + A > N || x + B > M;
}
let answer = bfs();
console.log(answer);
지속적인 성장