알고리즘/백준
3190_뱀
베리영young
2024. 6. 13. 17:13
사용 알고리즘: 구현 빡
사용 언어: java
map을 사용했을 때 (사과를 직접 map에다 찍어줌)
package src;
import java.awt.*;
import java.io.*;
import java.util.*;
public class Main_bj_3190_뱀 {
static int n, k, l; //맵 크기, 사과 개수, 방향 변환 횟수
static int[][] gameMap;
static int gameTime; //게임 시간
static PriorityQueue<DirectionInfo> changes = new PriorityQueue<>(((o1, o2) -> o1.time - o2.time)); //방향 전환 저장 배열
static ArrayList<Point> snakeBody = new ArrayList<>();
static int direction = 0; //처음엔 오른쪽
static int[] dx = {0,1,0,-1}; //+1: 오른쪽으로 90도 (동 남 서 북) -1: 왼쪽으로 90도
static int[] dy = {1,0,-1,0};
public static void main(String[] args) throws IOException {
input_3190();
snakeBody.add(new Point(0, 0));
while (true) {
gameTime++;
int cx = snakeBody.get(0).x;
int cy = snakeBody.get(0).y;
Point nextPoint = new Point(cx+dx[direction], cy+dy[direction]);
if( gameTheEnd(nextPoint) ) break; //종료조건 만족하면 답 출력하고 끝
//사과 있나 없나 확인 후, 뱀의 위치 조정
applesAndSnakeBody(nextPoint);
//방향 전환 확인하기
if (!changes.isEmpty() && gameTime == changes.peek().time) { //큐의 맨 앞에 있는 시간이랑 게임 시간이 같으면?
//방향 전환하기
changeDirection();
}
}
}
private static void changeDirection() {
DirectionInfo needChanging = changes.poll();
if (needChanging.rotate == 'D') { //오른쪽으로 돌려야 할 때
direction = (direction + 1) % 4;
}
else { //왼쪽으로 돌려야 할 때
direction--;
if( direction == -1 ) direction = 3;
}
}
private static void applesAndSnakeBody(Point nextPoint) {
if ( appleInNextPoint(nextPoint) ) { //다음 좌표에 사과가 있다면, 사과 좌표는 삭제하고 true 리턴
snakeBody.add(0, nextPoint); //몸 길이 늘리기 (머리를 맨 처음에 집어넣기)
}
else { //사과 없음
moveSnake(nextPoint); //뱀 이동
}
}
private static void moveSnake(Point nextPoint) {
int snakeSize = snakeBody.size();
snakeBody.add(0, nextPoint);
snakeBody.remove(snakeSize);
}
private static boolean appleInNextPoint(Point nextPoint) {
if (gameMap[nextPoint.x][nextPoint.y] == 1) { //사과가 있으면
gameMap[nextPoint.x][nextPoint.y] = 0; //사과 먹기
return true;
}
return false;
}
private static boolean gameTheEnd(Point nextPoint) {
if(nextPoint.x<0 || nextPoint.y<0 || nextPoint.x>=n || nextPoint.y>=n) {
System.out.println(gameTime);
return true;
} //벽에 부딪혀서 게임이 끝나는 경우
for (Point body : snakeBody) {
if (body.x == nextPoint.x && body.y == nextPoint.y) {
System.out.println(gameTime);
return true;
}
}
return false; //게임 진행
}
private static void input_3190() throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
gameMap = new int[n][n];
k = Integer.parseInt(br.readLine());
for (int i = 0; i < k; i++) {
st = new StringTokenizer(br.readLine());
gameMap[Integer.parseInt(st.nextToken()) - 1][Integer.parseInt(st.nextToken()) - 1] = 1 ; //사과 있는 곳은 1로 표시
}
l = Integer.parseInt(br.readLine());
for (int i = 0; i < l; i++) {
st = new StringTokenizer(br.readLine());
int time = Integer.parseInt(st.nextToken());
char dir = st.nextToken().charAt(0);
changes.add(new DirectionInfo(time, dir));
}
}
}
class DirectionInfo {
int time;
char rotate;
public DirectionInfo(int time, char rotate) {
this.time = time;
this.rotate = rotate;
}
}
map을 사용하지 않고, 사과 좌표 정보를 list에 넣어서 해볼라캤드만... 왜 안 되지?
아래는 map을 쓰지 않고 사과 자표 정보를 list에 넣어서 만든 거...
package src;
import java.awt.*;
import java.io.*;
import java.util.*;
public class Main_bj_3190_뱀 {
static int n, k, l; //맵 크기, 사과 개수, 방향 변환 횟수
static int gameTime; //게임 시간
static PriorityQueue<DirectionInfo> changes = new PriorityQueue<>(((o1, o2) -> o1.time - o2.time)); //방향 전환 저장 배열
static ArrayList<Point> apples = new ArrayList<>(); //사과 좌표
static ArrayList<Point> snakeBody = new ArrayList<>();
static int direction = 0; //처음엔 오른쪽
static int[] dx = {0,1,0,-1}; //+1: 오른쪽으로 90도 (동 남 서 북) -1: 왼쪽으로 90도
static int[] dy = {1,0,-1,0};
public static void main(String[] args) throws IOException {
input_3190();
snakeBody.add(new Point(0, 0));
while (true) {
gameTime++;
int cx = snakeBody.get(0).x;
int cy = snakeBody.get(0).y;
Point nextPoint = new Point(cx+dx[direction], cy+dy[direction]);
if( gameTheEnd(nextPoint) ) break; //종료조건 만족하면 답 출력하고 끝
//사과 있나 없나 확인 후, 뱀의 위치 조정
applesAndSnakeBody(nextPoint);
//방향 전환 확인하기
if (!changes.isEmpty() && gameTime == changes.peek().time) { //큐의 맨 앞에 있는 시간이랑 게임 시간이 같으면?
//방향 전환하기
changeDirection();
}
}
}
private static void changeDirection() {
DirectionInfo needChanging = changes.poll();
if (needChanging.rotate == 'D') { //오른쪽으로 돌려야 할 때
direction = (direction + 1) % 4;
}
else { //왼쪽으로 돌려야 할 때
direction--;
if( direction == -1 ) direction = 3;
}
}
private static void applesAndSnakeBody(Point nextPoint) {
if ( appleInNextPoint(nextPoint) ) { //다음 좌표에 사과가 있다면, 사과 좌표는 삭제하고 true 리턴
snakeBody.add(0, nextPoint); //몸 길이 늘리기 (머리를 맨 처음에 집어넣기)
}
else { //사과 없음
moveSnake(nextPoint); //뱀 이동
}
}
private static void moveSnake(Point nextPoint) {
int snakeSize = snakeBody.size();
snakeBody.add(0, nextPoint);
snakeBody.remove(snakeSize);
}
private static boolean appleInNextPoint(Point nextPoint) {
for(int i=0; i<apples.size(); i++) {
if (apples.get(i).x == nextPoint.x && apples.get(i).y == nextPoint.y) {
apples.remove(i);
return true;
}
}
return false;
}
private static boolean gameTheEnd(Point nextPoint) {
if(nextPoint.x<0 || nextPoint.y<0 || nextPoint.x>=n || nextPoint.y>=n) {
System.out.println(gameTime);
return true;
} //벽에 부딪혀서 게임이 끝나는 경우
for (Point body : snakeBody) {
if (body.x == nextPoint.x && body.y == nextPoint.y) {
System.out.println(gameTime);
return true;
}
}
return false; //게임 진행
}
private static void input_3190() throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
k = Integer.parseInt(br.readLine());
for (int i = 0; i < k; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken()) - 1;
int y = Integer.parseInt(st.nextToken()) - 1;
apples.add(new Point(x, y));
}
l = Integer.parseInt(br.readLine());
for (int i = 0; i < l; i++) {
st = new StringTokenizer(br.readLine());
int time = Integer.parseInt(st.nextToken());
char dir = st.nextToken().charAt(0);
changes.add(new DirectionInfo(time, dir));
}
}
}
class DirectionInfo {
int time;
char rotate;
public DirectionInfo(int time, char rotate) {
this.time = time;
this.rotate = rotate;
}
}
움직이는 좌표에 사과가 있나 확인할 때,
map은 한 방에 확인이 가능한데,
list를 쓰게 되면, 운이 나쁠 땐 list의 마지막 인덱스까지 돌아야 해서
시간 효율 상 map이 나을 듯...