뱀
📚 문제 설명
N * N 의 보드가 있고 보드에 사과가 있다.
이 보드 위에서 뱀이 매초 움직일 때, 게임이 끝나는 시간을 구해라.
뱀의 움직임
- 앞에 사과가 있으면 꼬리 위치 유지, 머리만 움직임 ( 뱀의 길이가 늘어남 )
- 앞에 사과가 없으면 뱀의 길이를 유지, 앞으로 한칸 이동 ( 뱀의 길이는 유지 )
- 뱀의 방향 전환은
[시간, 방향]으로 주어진다.
게임 종료 조건
- 뱀이 벽에 부딪혔을 때
- 뱀이 자기 몸에 부딪혔을 때
-입력-
보드의 크기
사과 갯수
사과 위치
...
뱀의 방향 전환 횟수
뱀의 방향 전환
...
👨🏻💻 풀이 과정
이 문제에서는 뱀을 DEQUE(덱)으로 생각하면 조금 편하다.
| 뱀의 움직임 | DEQUE(덱) 에서 구현 |
|---|---|
| 사과 O | DEQUE 앞부분에 Push |
| 사과 X | DEQUE 앞부분에 Push, 뒷부분 Pop |
그럼 이제 게임 종료 조건을 생각해 보자.
- 보드 끝에 있는 벽에 닿을 때
- 뱀 몸에 닿을 때
여기까지 생각하고 전체적 로직을 확인하면 다음과 같다.
map에 사과 정보를 입력SnakeOrder에 뱀의 방향 전환 정보 저장- 충돌이 일어날 때까지 반복문 진행
- 시간 계산후 방향 전환시
direction값을 변경 - 뱀의 다음위치 계산
- 다음 위치의 충돌 여부 계산
- 보드 밖으로 나갔는가
- 뱀 몸에 닿았는가
- 사과에 따른 뱀의 움직임
DEQUE에push혹은pop
- 시간 계산후 방향 전환시
solution 로직 구현
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
let N = parseInt(input.shift());
let AppleNumber = parseInt(input.shift());
let map = new Array(N);
for (let i = 0; i < N; i++) {
map[i] = new Array(N).fill(0);
}
// 사과 위치를 map에 입력
for (let i = 0; i < AppleNumber; i++) {
const [x, y] = input.shift().split(' ').map(Number);
map[x - 1][y - 1] = 1;
}
let SnakeMovement = parseInt(input.shift());
//뱀의 움직임 저장 배열
let SnakeOrder = [];
// 뱀의 움직임을 배열로 저장
for (let i = 0; i < SnakeMovement; i++) {
SnakeOrder.push(input.shift().split(' ').map((Value, Index) => {
if (Index === 0) return parseInt(Value);
return Value;
}));
}
class NODE {
//생략
}
class DEQUE {
//생략
}
const solution = () => {
// DEQUE 선언
const Snake = new DEQUE();
// 뱀의 시작 위치
let nowX = 0;
let nowY = 0;
Snake.PushFront([nowX, nowY]);
// 시간
let cnt = 0;
// 뱀의 진행 방향을 표시
let direction = 1;
let dx = [1, 0, -1, 0,];
let dy = [0, 1, 0, -1];
// 뱀의 충돌 여부 확인
let collision = false;
// 뱀 방향 전환을 위한 [초, 방향] 저장
let [M, Order] = SnakeOrder[0];
while (!collision) {
// 만약 방향 전환 시간이 되었다면
if (cnt === M) {
// 방향 전환 실시
if (Order === 'D') {
direction = (direction - 1 + dx.length) % dx.length;
} else {
direction = (direction + 1) % dx.length;
}
SnakeOrder.shift();
// 방향 전환 완료후 다음 방향 전환을 위해 변수 변경
if (SnakeOrder.length) {
[M, Order] = SnakeOrder[0];
}
}
// 뱀의 다음 위치
const nextX = nowX + dx[direction];
const nextY = nowY + dy[direction];
cnt++;
// 만약 벽과 충돌 혹은 뱀의 몸과 충돌할 경우 종료
if (nextX >= N || nextY >= N || nextY < 0 || nextX < 0 || Snake.Has(nextX,nextY)) {
collision = true;
break;
}
// 다음 위치에 사과가 없다면
if (map[nextX][nextY] === 0) {
Snake.PushFront([nextX, nextY]);
Snake.PopEnd();
} else { // 사과가 있을 때
// 사과는 뱀이 먹기 때문에 0으로
map[nextX][nextY] = 0;
Snake.PushFront([nextX, nextY]);
}
// 뱀의 현재 위치 변경
nowX = nextX;
nowY = nextY;
}
return cnt;
};
console.log(solution());그 후 이제 연결 리스트 구조를 이용하여 DEQUE(덱)을 구현하면 되는데 자세한 구현에 대한 설명은 이전 포스트를 참고하길 바란다.
DEQUE(덱) 구현
class NODE {
constructor(item) {
this.node = item;
this.prev = null;
this.next = null;
}
}
//연결 리스트를 이용하여 구현
class DEQUE {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
PushFront(item) {
const PushElement = new NODE(item);
// 만약 한개의 원소만 있으면 시작과 끝은 같기 때문
if (this.length === 0) {
this.head = PushElement;
this.tail = PushElement;
} else {
// 시작 부분 이전에 붙여주고 시작 부분을 변경해주는 방식
this.head.prev = PushElement;
PushElement.next = this.head;
this.head = PushElement;
}
this.length++;
}
// 이 부분은 사용하지 않아서 제거 예정
PushEnd(item) {
const PushElement = new NODE(item);
if (this.length === 0) {
this.head = PushElement;
this.tail = PushElement;
} else {
this.tail.next = PushElement;
PushElement.prev = this.tail;
this.tail = PushElement;
}
this.length++;
}
// 이 부분은 사용하지 않아서 제거 예정
PopFront() {
if (this.length === 0) return;
const PopElement = this.head;
this.head = this.head.next;
if (this.length === 1) {
this.head = null;
this.tail = null;
} else {
this.head.prev = null;
}
this.length--;
return PopElement;
}
PopEnd() {
// 길이가 0이면 pop을 해줄 수 없음
if (this.length === 0) return;
// 끝부분을 pop하고 끝부분의 위치를 이전으로 변경
const PopElement = this.tail;
this.tail = this.tail.prev;
// 만약 길이가 1이었으면 큐는 비어야함
if (this.length === 1) {
this.head = null;
this.tail = null;
} else {
//끝부분의 마지막 부분 연결을 해제
this.tail.next = null;
}
this.length--;
return PopElement;
}
Has(x, y) {
// 시작 부분을 기억하기 위해
const remember = this.head;
// 반복문을 돌며 일치 여부를 직접 확인
for (let i = 0; i < this.length; i++) {
if (this.head.node[0] === x && this.head.node[1] === y) {
return true;
}
// 다음 위치 확인
this.head = this.head.next;
}
// 확인을 완료했으면 다시 시작부분을 가리키게
this.head = remember;
return false;
}
}전체 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
let N = parseInt(input.shift());
let AppleNumber = parseInt(input.shift());
let map = new Array(N);
for (let i = 0; i < N; i++) {
map[i] = new Array(N).fill(0);
}
// 사과 위치를 map에 입력
for (let i = 0; i < AppleNumber; i++) {
const [x, y] = input.shift().split(' ').map(Number);
map[x - 1][y - 1] = 1;
}
let SnakeMovement = parseInt(input.shift());
//뱀의 움직임 저장 배열
let SnakeOrder = [];
// 뱀의 움직임을 배열로 저장
for (let i = 0; i < SnakeMovement; i++) {
SnakeOrder.push(input.shift().split(' ').map((Value, Index) => {
if (Index === 0) return parseInt(Value);
return Value;
}));
}
class NODE {
constructor(item) {
this.node = item;
this.prev = null;
this.next = null;
}
}
//연결 리스트를 이용하여 구현
class DEQUE {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
PushFront(item) {
const PushElement = new NODE(item);
// 만약 한개의 원소만 있으면 시작과 끝은 같기 때문
if (this.length === 0) {
this.head = PushElement;
this.tail = PushElement;
} else {
// 시작 부분 이전에 붙여주고 시작 부분을 변경해주는 방식
this.head.prev = PushElement;
PushElement.next = this.head;
this.head = PushElement;
}
this.length++;
}
PopEnd() {
// 길이가 0이면 pop을 해줄 수 없음
if (this.length === 0) return;
// 끝부분을 pop하고 끝부분의 위치를 이전으로 변경
const PopElement = this.tail;
this.tail = this.tail.prev;
// 만약 길이가 1이었으면 큐는 비어야함
if (this.length === 1) {
this.head = null;
this.tail = null;
} else {
//끝부분의 마지막 부분 연결을 해제
this.tail.next = null;
}
this.length--;
return PopElement;
}
Has(x, y) {
// 시작 부분을 기억하기 위해
const remember = this.head;
// 반복문을 돌며 일치 여부를 직접 확인
for (let i = 0; i < this.length; i++) {
if (this.head.node[0] === x && this.head.node[1] === y) {
return true;
}
// 다음 위치 확인
this.head = this.head.next;
}
// 확인을 완료했으면 다시 시작부분을 가리키게
this.head = remember;
return false;
}
}
const solution = () => {
// DEQUE 선언
const Snake = new DEQUE();
// 뱀의 시작 위치
let nowX = 0;
let nowY = 0;
Snake.PushFront([nowX, nowY]);
// 시간
let cnt = 0;
// 뱀의 진행 방향을 표시
let direction = 1;
let dx = [1, 0, -1, 0,];
let dy = [0, 1, 0, -1];
// 뱀의 충돌 여부 확인
let collision = false;
// 뱀 방향 전환을 위한 [초, 방향] 저장
let [M, Order] = SnakeOrder[0];
while (!collision) {
// 만약 방향 전환 시간이 되었다면
if (cnt === M) {
// 방향 전환 실시
if (Order === 'D') {
direction = (direction - 1 + dx.length) % dx.length;
} else {
direction = (direction + 1) % dx.length;
}
SnakeOrder.shift();
// 방향 전환 완료후 다음 방향 전환을 위해 변수 변경
if (SnakeOrder.length) {
[M, Order] = SnakeOrder[0];
}
}
// 뱀의 다음 위치
const nextX = nowX + dx[direction];
const nextY = nowY + dy[direction];
cnt++;
// 만약 벽과 충돌 혹은 뱀의 몸과 충돌할 경우 종료
if (nextX >= N || nextY >= N || nextY < 0 || nextX < 0 || Snake.Has(nextX,nextY)) {
collision = true;
break;
}
// 다음 위치에 사과가 없다면
if (map[nextX][nextY] === 0) {
Snake.PushFront([nextX, nextY]);
Snake.PopEnd();
} else { // 사과가 있을 때
// 사과는 뱀이 먹기 때문에 0으로
map[nextX][nextY] = 0;
Snake.PushFront([nextX, nextY]);
}
// 뱀의 현재 위치 변경
nowX = nextX;
nowY = nextY;
}
return cnt;
};
console.log(solution());🧐 후기
문제 설명을 읽고 처음에는 미처 DEQUE(덱)을 이용하는 문제인지 눈치채지 못했고, 알고리즘 분류를 확인하고서야 DEQUE(덱)을 사용하는 문제라는 것을 깨닫고 풀이를 진행했다.
막상 DEQUE(덱)를 사용해야 한다는 것을 알고 나니 풀이는 오래 걸리지 않았다.
아직 문제를 읽고 어떤 알고리즘인지 파악하는 눈이 부족한 것 같다.
JavaScript를 사용하는 모두를 위해...