백준 3190번: 뱀
문제 설명
- 사과를 먹으면 몸의 길이가 1 길어집니다.
- 주어진 조건대로 움직였을 때 몇초 뒤에 벽이나 자신의 몸에 닿는지를 구하는 문제입니다.
접근법
- 이전에 움직였던 좌표들을 뱀의 길이만큼 기억하게 했습니다.
- 뱀의 길이가 3이면 현재 뱀이 밟고있는 위치는 현재의(x,y), 1초 전의(x,y), 2초 전의(x,y)가 됩니다.
정답
import java.io.*;
import java.util.*;
public class Main {
static int[] dx = { 0, 1, 0, -1 }; // 우 하 좌 상
static int[] dy = { 1, 0, -1, 0 };
static int N, time;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
int[][] board = new int[N][N]; // 보드를 만듭니다.
int K = Integer.parseInt(br.readLine());
// 보드에 사과를 놓습니다.(1이면 사과가 놓여있다는 뜻입니다)
StringTokenizer st = null;
for (int k = 0; k < K; k++) {
st = new StringTokenizer(br.readLine(), " ");
int row = Integer.parseInt(st.nextToken());
int col = Integer.parseInt(st.nextToken());
board[row - 1][col - 1] = 1; // 입력은 인덱스가 1부터 시작하므로 1을 뺐습니다.
}
int L = Integer.parseInt(br.readLine());
Deque<turn> deq = new LinkedList<turn>(); // 방향변환정보를 담을 변수입니다.
// 방향변환정보를 deq에 담습니다.
for (int l = 0; l < L; l++) {
st = new StringTokenizer(br.readLine());
int X = Integer.parseInt(st.nextToken());
char C = st.nextToken().charAt(0);
deq.add(new turn(X, C));
}
// 뱀을 만듭니다.
Snake snake = new Snake(1, 0, 0, new LinkedList<int[]>());
// 시작점을 설정합니다
int[] start = { 0, 0 };
snake.trace.add(start);
int d = 0; // 현재 진행방향을 나타내는 변수입니다.
while (true) {
// 시간이 흐릅니다.
++time;
// 현재방향(d)으로 전진합니다.
int nx = snake.x + dx[d];
int ny = snake.y + dy[d];
int[] temp = { nx, ny };
// 보드를 벗어나거나 자신의 몸에 닿으면 종료합니다.
if (0 > nx || nx >= N || 0 > ny || ny >= N || touch_test(snake, temp)) break;
// 보드에 사과가 있으면 사과를 먹고 길이가 1 증가합니다.
if (board[nx][ny] == 1) {
snake.length++;
board[nx][ny] = 0;
}
// 뱀의 위치를 변경시켜줍니다.
snake.x = nx;
snake.y = ny;
// 사과를 먹으면 뱀의 길이가 길어지는 게 아니라 머리가 움직인 칸을 더 많이 기억하도록(?) 구현했습니다.
// snake.trace의 길이를 항상 snake.length로 유지합니다.
if (snake.length > snake.trace.size()) {
snake.trace.add(temp);
} else if (snake.length == snake.trace.size()) {
snake.trace.remove(0); // 기존의 값을 지우고
snake.trace.add(temp); // 새로운 값을 넣습니다.
}
// 방향변환정보를 체크합니다.
if (!deq.isEmpty() && time == deq.peekFirst().X) { // 현재시간이 X초라면 방향을 변경합니다
if (deq.peekFirst().C == 'D') { // D면
d = (d + 1) % 4; // 오른쪽으로 돕니다.
} else { // L이면
d = (4 + d - 1) % 4; // 왼쪽으로 돕니다.
}
deq.pollFirst(); // 방향을 변환했기 때문에 deq에서 제거합니다.
}
}
System.out.println(time);
}
// 뱀이 자신의 몸에 닿았는지 확인하는 메서드 입니다.
public static boolean touch_test(Snake snake, int[] temp) {
int x = temp[0];
int y = temp[1];
// 처음에 contains메서드를 썼는데 각자가 다른 객체라 원하는 결과값이 나오지 않았습니다.
// 그래서 for문을 통해 각각의 값을 비교하는 방법으로 변경했습니다.
for (int i = 0; i < snake.trace.size(); i++) {
int tx = snake.trace.get(i)[0];
int ty = snake.trace.get(i)[1];
if (x == tx && y == ty)
return true;
}
return false;
}
// 방향변환 변수를 담는 객체입니다.
static class turn {
int X;
char C;
public turn(int X, char C) {
super();
this.X = X;
this.C = C;
}
@Override
public String toString() {
return "turn [X=" + X + ", C=" + C + "]";
}
}
// 뱀의 길이(length), 위치(x,y), 현재 닿아있는 칸(trace) 변수를 담은 객체입니다.
static class Snake {
int length;
int x;
int y;
List<int[]> trace; // 뱀의 길이가 3이면 현재 뱀이 밟고있는 위치는 현재의(x,y), 1초 전의(x,y), 2초 전의(x,y)가 됩니다.
public Snake(int length, int x, int y, List<int[]> trace) {
super();
this.length = length;
this.x = x;
this.y = y;
this.trace = trace;
}
}
}
기타
- turn은 굳이 객체로 사용할 필요 없었던거 같다.
Author And Source
이 문제에 관하여(백준 3190번: 뱀), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@qwerty1434/백준-3190번-뱀저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)