[백준 3190] 뱀 / 자바 / 구현

문제         

레벨: G5
알고리즘: 구현 + 큐 
풀이시간: 1:30
힌트 참조 유무: 무

https://www.acmicpc.net/problem/3190

1 번째 시도: 성공   

[예제 그림]

초에 해당하는 뱀의 머리 위치를 그림으로 그려봤다.

x는 사과의 위치다.

예제1, 예제2

예제3

[알고리즘 설명]

이 문제는 구현 문제이다.

while 문 안에 있는 조건들을 어떻게 잘 구현했는지, 자료구조를 적절히 잘 사용했는지가 관건이다. 

설명은 주석을 참조바란다.

 

뱀의 몸통을 담기 위해 snake큐

명령을 담기 위한 moves큐 

 

문제를 다 풀고 나서 한가지 생각해본 점은 명령을 담기 위한 자료구조를 큐 말고 HashMap을 썼다면 ntdir,ntsec를 안썼어도 됐다는 거다. 변수가 줄어들수록 코드의 유지보수가 쉽다고 생각하기 때문에 다음부터 더 신중히 자료구조를 선택해야겠다.

+)주의
헷갈리면 안되는 것은 뱀이 이동하고 나서 방향을 튼다는 것이다. 예제 1의 8초라고 한다면, 8까지의 위치를 가고 나서 머리를 회전하는 것이다. 당연히 구현도 그렇게 해야한다.

[고민]

• 뱀의 머리 회전을 어떻게 구현할 것인가 
  • dx,dy에  +1(시계방향)    or     +3(반시계방향)    후  %4를 해준다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int appleN = Integer.parseInt(br.readLine());

        //시계방향
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        int[][] arr = new int[N][N];

        for (int i = 0; i < appleN; i++) {
            String[] s = br.readLine().split(" ");
            arr[Integer.parseInt(s[0])-1][Integer.parseInt(s[1])-1] = 1;
        }

        int commandN = Integer.parseInt(br.readLine());

        Queue<Move> moves = new LinkedList<>();
        for (int i = 0; i < commandN; i++) {
            String[] s1 = br.readLine().split(" ");
            moves.add(new Move(Integer.parseInt(s1[0]), s1[1]));
        }
        
        //다음 명령을 위한
        Move poll = moves.poll();
        int ntsec = poll.sec;
        String ntdir = poll.dir;
        
        //현재정보
        int nowSec = 0;
        int x = 0;
        int y = 0;
        int directionInd = 0;
        String dir;
        
        //뱀 몸통의 정보
        Queue<int[]> snake = new LinkedList<int[]>();
        snake.add(new int[] {0,0});
        
        while (true) {
            //1초 흐름
            nowSec++;

            //방향에 따른 증감
            x = x + dx[directionInd];
            y = y + dy[directionInd];
            
            //벽 부딪힐시 게임 종료
            if (x < 0 || x >= N || y < 0 || y >= N)
                break;
            //자기 몸에 부딪힐시 게임 종료
            if (contains(snake, x, y))
                break;

            //뱀 머리 이동
            snake.add(new int[]{x, y});

            //사과가 있을때
            if (arr[y][x] == 1) {
                arr[y][x] = 0;
            }
            else {
                    snake.poll();
            }

            //명령 실행 시간이라면 방향 바꿔주기
            if (nowSec == ntsec) {
                dir = ntdir;
                //방향에 따른 인덱스 증감
                if (dir.equals("D")) {
                    directionInd = (directionInd + 1) % 4;
                } else if (dir.equals("L")) {
                    directionInd = (directionInd + 3) % 4;
                }
                if(!moves.isEmpty()) {
                    poll = moves.poll();
                    ntsec = poll.sec;
                    ntdir = poll.dir;
                }
            }
        }
        System.out.println(nowSec);
    }

    private static boolean contains(Queue<int[]> snake, int x, int y) {
        for (int[] body : snake) {
            if (body[0] == x && body[1] == y) {
                return true;
            }
        }
        return false;
    }

    //명령
    public static class Move {
        int sec;
        String dir;

        public Move(int sec, String dir) {
            this.sec = sec;
            this.dir = dir;
        }
    }
}