[백준] 3190번 뱀 (Java)

백준 3190번 뱀: https://www.acmicpc.net/problem/3190

3190번: 뱀

 

아이디어

구현에는 뱀의 몸통 정보를 담은 LinkedList<int[]> snake와 보드판인 int[] board가 사용된다.

초기에 snake에는 {0,0}이 들어 있으며, 뱀이 움직일 때마다 해당 위치를 add() 한다.

만약 뱀이 사과를 먹지 않았다면 뱀의 몸 길이는 유지 되어야 하므로 remove(0) 해서 꼬리를 잘라준다.

사과의 위치는 보드판에 1로 표시해서 구분하였다.

 

뱀의 이동 위치와 관련해서 dx, dy를 사용했다.

index	0	1	2	3
방향	→	↓	←	↑
dx	0	1	0	-1
dy	1	0	-1	0

초기 방향이 오른쪽이므로 index = 0으로 시작한다.

입력에 D가 나오면 오른쪽으로 회전이므로 index를 1 증가한다. 반대로 L이 나오면 왼쪽으로 회전이므로 index를 1 감소한다.

이와 관련해서는 nextDir() 함수를 작성해 사용했다.

 

뱀은 보드판 밖으로 나가거나 뱀의 몸통을 지나친다면 게임이 끝나므로 해당 로직은 isFinish() 함수로 따로 작성했다.

 

 

코드

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {
    private static int[] dx = {0, 1, 0, -1};
    private static int[] dy = {1, 0, -1, 0};
    private static int n, l, k;
    private static int[][] board;
    private static List<int[]> snake;

    public static void main(String[] args) {
        snake = new LinkedList<>();
        snake.add(new int[]{0, 0});

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        board = new int[n][n];

        k = sc.nextInt();
        for (int i = 0; i < k; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            board[x - 1][y - 1] = 1; // 사과의 위치 설정
        }

        l = sc.nextInt();
        int[][] dir = new int[l][2];
        for (int i = 0; i < l; i++) {
            dir[i][0] = sc.nextInt();
            char temp = sc.next().charAt(0);
            dir[i][1] = (temp == 'L') ? -1 : 1; // L -> -1, D -> 1
        }

        int time = solution(0, 0, 0, dir);
        System.out.println(time);
    }

    private static int solution(int curX, int curY, int currentDir, int[][] dir) {
        int time = 0;
        int turn = 0;
        
        while (true) {
            time++;
            int nextX = curX + dx[currentDir];
            int nextY = curY + dy[currentDir];

            if (isFinish(nextX, nextY)) break;

            if (board[nextX][nextY] == 2) { // 사과를 먹으면
                snake.add(new int[]{nextX, nextY});
            } else {
                snake.add(new int[]{nextX, nextY});
                snake.remove(0); // snake 꼬리 제거
            }

            curX = nextX;
            curY = nextY;

            if (turn < l) {
                if (time == dir[turn][0]) { // 다음 방향 설정
                    currentDir = nextDir(currentDir, dir[turn][1]);
                    turn++;
                }
            }
        }
        return time;
    }

    private static int nextDir(int current, int dir) { // current 현재, dir 다음 방향
        int next = (current + dir) % 4;
        if (next == -1) next = 3;

        return next;
    }

    private static boolean isFinish(int x, int y) {
        if (x == -1 || x == n || y == -1 || y == n) { // 다음 위치가 보드판 밖으로 나갔는지
            return true;
        }
        for (int i = 0; i < snake.size(); i++) { // 뱀 몸통이랑 닿았는지
            int[] s = snake.get(i);
            if (s[0] == x && s[1] == y) return true;
        }
        return false;
    }
}