Problem
사과의 위치와 뱀의 이동 경로가 주어질 때 게임이 끝나는 초(second)를 구하는 문제입니다.
Solution
특별한 알고리즘은 사용하지 않고 문제에서 제시한 대로 구현만 하는 시뮬레이션 문제입니다.
조건을 살펴보면
- 뱀의 머리는 무조건 이동한다
- 뱀의 머리가 있는 곳에 사과가 있으면 꼬리 위치는 그대로
- 뱀의 머리가 있는 곳에 사과가 없으면 없으면 꼬리를 잘라낸다.
- 뱀의 머리가 있는 곳에 벽이나 뱀의 몸이 있다면 게임이 끝난다.
이렇게 총 4가지의 조건을 구현하면 됩니다.
오른쪽 왼쪽으로 방향을 바꾸는 건 % 연산자를 사용하면 쉽게 할 수 있습니다.
왼쪽으로 돌리기 = (현재 방향 + 3) % 4
오른쪽으로 돌리기 = (현재 방향 + 1) % 4
대신 처음 dx, dy 배열을 북, 동, 남, 서 순서처럼 시계방향 또는 반시계 방향으로 설정해야 합니다.
인덱스가 0, 1, 2, 3 에서 반복된다는 점을 활용하면 % 4 연산자를 통해 다음 방향 인덱스를 쉽게 구할 수 있습니다.
뱀의 몸통을 기억하는 방법은 Deque 자료구조를 사용하였습니다.
Deque는 Queue나 Stack과 달리 리스트의 앞, 뒤에서 삽입/삭제가 가능한 자료구조입니다.
Deque 자체를 뱀의 몸이라고 생각하면서 꼬리를 삭제할때는 removeLast(), 머리를 이동시킬때는 addFirst()를 사용하면 됩니다.
Java Code
import java.util.*;
import java.io.*;
class Main {
static int stoi(String s) {
return Integer.parseInt(s);
}
static class Dot {
int x, y;
public Dot(int x, int y) {
this.x = x;
this.y = y;
}
}
static int n;
static int K;
static int[][] map;
static int L;
static int[] time;
static int[] dir;
static int[] dx = {-1, 0, 1, 0}; // 북동남서
static int[] dy = {0, 1, 0, -1};
static Deque<Dot> snake = new ArrayDeque<Dot>();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = stoi(br.readLine());
K = stoi(br.readLine());
map = new int[n + 1][n + 1]; // 맨 위 맨 좌측은 (1,1)
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
int v1 = stoi(st.nextToken());
int v2 = stoi(st.nextToken());
map[v1][v2] = 1; // 사과 위치는 1
}
L = stoi(br.readLine());
time = new int[L];
dir = new int[L];
for (int i = 0; i < L; i++) {
st = new StringTokenizer(br.readLine());
time[i] = stoi(st.nextToken());
dir[i] = getDirection(st.nextToken());
}
// 문제 풀이
solution();
}
static void solution() {
int second = 0;
int snakeDir = 1; // 첫 방향은 오른쪽
int timeIdx = 0;
map[1][1] = 2; // 처음 뱀의 위치는 (1,1)
snake.add(new Dot(1, 1));
while (true) {
// 시간이 지나면 방향 바꾸기
if (timeIdx < L && time[timeIdx] == second) {
snakeDir = (snakeDir + dir[timeIdx]) % 4;
timeIdx++;
}
// 1. 몸길이를 늘려 머리를 다음 칸에 위치시킨다
int nx = snake.getFirst().x + dx[snakeDir];
int ny = snake.getFirst().y + dy[snakeDir];
// 몸이나 벽과 부딪히면 게임 끝
if (nx <= 0 || nx > n || ny <= 0 || ny > n) {
System.out.println(second + 1);
break;
}
if (map[nx][ny] == 2) {
System.out.println(second + 1);
break;
}
if (map[nx][ny] == 1) {
// 2. 만약 이동한 칸에 사과가 있다면, 사과 없어지고 꼬리 그대로 머리 추가
map[nx][ny] = 2;
snake.addFirst(new Dot(nx, ny));
}
else if (map[nx][ny] == 0) {
// 3. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여 꼬리가 위치한 칸 비우기
map[nx][ny] = 2;
snake.addFirst(new Dot(nx, ny));
Dot tail = snake.removeLast();
map[tail.x][tail.y] = 0;
}
second++;
}
}
// 오른쪽은 1 왼쪽은 3
static int getDirection(String s) {
if (s.equals("D"))
return 1;
else
return 3;
}
}Python Code
# -*- coding: utf-8 -*-
import sys
import collections
N = 0
arr = []
## 북 동 남 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
snakes = collections.deque([[1,1]])
def printX():
print()
for i in range(1, N+1):
for j in range(1, N+1):
print(arr[i][j], end=" ")
print()
def snake_move(direction):
[x, y] = snakes[0]
nx = x + dx[direction]
ny = y + dy[direction]
## 머리가 몸통에 부딪히면 종료
if [nx, ny] in snakes:
return True
## 벽에 부딪히면 종료
if nx <= 0 or nx > N or ny <= 0 or ny > N:
return True
## 이동한 칸에 아무것도 없으면 꼬리를 줄여줌
if arr[nx][ny] == 0:
[ex, ey] = snakes.pop()
arr[ex][ey] = 0
## 이동한 칸에 사과가 있으면 없애고 몸을 늘린다
snakes.appendleft([nx, ny])
arr[nx][ny] = 1
return False
def rotate(s, d):
## L이면 왼쪽 D면 오른쪽
if s == "L":
return (d+3)%4
else:
return (d+1)%4
def solve(move, L):
idx = 0
direction = 1 ## 초기 방향은 오른쪽
time = 0
while True:
if idx < L:
if move[idx][0] == time:
direction = rotate(move[idx][1], direction)
idx += 1
if snake_move(direction) == True:
print(time+1)
return
time += 1
if __name__ == '__main__':
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
arr = [[0]*(N+1) for i in range(N+1)]
for i in range(K):
v1, v2 = map(int, sys.stdin.readline().split())
arr[v1][v2] = 2
L = int(sys.stdin.readline())
move = []
for i in range(L):
X, C = sys.stdin.readline().split()
move.append([int(X), C])
## 처음 뱀 위치
arr[1][1] = 1
solve(move, L)'알고리즘 문제 > Samsung' 카테고리의 다른 글
| 백준 14889번. 스타트와 링크 (Java, Python) (0) | 2018.12.29 |
|---|---|
| 백준 14503번. 로봇 청소기 (Java, Python) (1) | 2018.12.29 |
| 백준 14502번. 연구소 (Java, Python) (5) | 2018.12.28 |
| 백준 14500번. 테트로미노 (Java, Python) (2) | 2018.12.27 |
| 백준 14888번. 연산자 끼워넣기 (Java, Python) (0) | 2018.12.27 |
