[BOJ] 3190 뱀

✨ 구현 ➔ '큐' 이용하기 

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

3190번: 뱀

---

📍 고려해야할 점

• 자료구조 '큐'의 특성을 이용해서 풀기
• 뱀의 머리를 먼저 이동시켜 몸길이 늘리기
• 해당하는 칸에 사과가 있으면 사과를 먹고 사과를 없애주기
• 뱀의 꼬리가 아닌 몸통을 만나면 끝내기 ➔ return !!
• 벽에 닿으면 끝내기 ➔ return !!
• 뱀은 (1, 1)에 존재
• 행, 열 잘 구분하기 ! 
• 방향 바꿀 때 효율적인 방법 생각해보기 

 

🕹️ 풀이과정 

1️⃣  행, 열에 대한 정보를 참고해서 사과가 있는 곳을 1로 둔다. 

2️⃣ 방향 변환에 대한 정보를 Queue에 저장한다.

💡 방향변환 정보는 int형인 시간과 char형인 방향이 포함되어야 하므로 제네릭 타입을 Info로 설정한다. 

3️⃣ game() 는 뱀을 이동시키는 함수이며 이동한 좌표를 Deque에 저장한다.
💡 뱀의 꼬리와 머리를 이동시켜야 하기 때문에 앞, 뒤로 요소들을 추가 및 삭제를 할 수 있는 자료구조인 Deque을 사용했다. 

4️⃣ Deque에 현재 위치 (1, 1)를 저장하고, 오른쪽 방향을 바라보고 있기 때문에 현재 방향을 '동'쪽으로 둔다. (nowDir = 1) 

💡 북, 동, 남, 서를 0, 1, 2, 3으로 생각하고 풀기 ➔ BOJ_14503_로봇청소기 참고 

5️⃣ 가장 최근에 삽입된 것 (= 뱀의 머리 부분)을 기준으로 현재 바라보고 있는 방향에 대해 머리를 이동시켜 몸길이를 늘리고 시간도 증가시킨다. 

6️⃣ 벽에 닿거나 뱀 본인의 몸에 닿으면 게임이 끝나므로 이동된 위치를 확인한다. 

7️⃣ 이동 가능하다면 이동된 위치에 사과가 있는지 확인한다. 사과가 있다면 사과를 먹고 없애버린다. (board[nx][ny]=0)

사과가 없다면 꼬리가 위치한 부분을 없애서 몸길이를 유지시킨다. 꼬리 부분은 가장 먼저 삽입된 것이므로 pollFirst()를 사용한다. 

8️⃣ 만약, 게임을 시작한지 특정 시간만큼 지났다면 방향을 바꿔준다. 방향변환 정보가 더 있다면 새로 갱신하고, 없다면 그대로 간다. 

 

---

✨ 방향 바꿀 때 팁 !!

if (timeCnt == t) { // 방향 바꿀 시간~~
                if (d == 'D') { // 오른쪽
                    nowDir = (nowDir+1)%4; // 북➔동➔남➔서 0,1,2,3
                } else { // 왼쪽
                    nowDir = (nowDir+3)%4; // 북➔서➔남➔동 0,3,2,1
                }
                if (!direction.isEmpty()) {
                    directInfo = direction.poll();
                    t = directInfo.time;
                    d = directInfo.dir;
                }
            }

 

 

👩‍💻 전체 코드 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
public class BOJ_3190_뱀 {

    static int N, K, L, timeCnt;
    static int[][] board;
    static Queue<DirectInfo> direction;
    static int[] dx = {-1, 0, 1, 0}; // 북동남서 -> 0123
    static int[] dy = {0, 1, 0, -1};
    
    static class DirectInfo{
        int time;
        char dir;

        public DirectInfo(int time, char dir) {
            this.time = time;
            this.dir = dir;
        }
    }

    static class Info{
        int x, y;

        public Info(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static void game(){
        Deque<Info> deq = new LinkedList<>();
        deq.add(new Info(1, 1));

        int nowDir = 1; // 동쪽(오른쪽) 바라보고 있음
        DirectInfo directInfo = direction.poll();

        int t=directInfo.time;
        char d = directInfo.dir;

        while(!deq.isEmpty()){

            Info info = deq.peekLast(); // 가장 최근에 삽입된 것 확인

            // 몸길이 늘리기
            int nx = info.x + dx[nowDir];
            int ny = info.y + dy[nowDir];

            timeCnt++;

            // 벽에 닿거나 뱀이 본인 몸에 닿으면 끝 !
            if (nx > 0 && ny > 0 && nx <= N && ny <= N) { // 벽에 안닿긴 함 -> 몸에 닿는지 확인
                for (Info element : deq) {
                    if (nx == element.x && ny == element.y) {
                        return;
                    }
                }
            }else{ // 벽에 닿음 -> 끝
                return;
            }

            // 사과가 있을 때 길이 늘어나기 && 사과 없으면 꼬리 부분 지우기
            if (board[nx][ny] != 1) { // 사과 없음 -> 꼬리가 위치한 부분 없애기
                deq.pollFirst();
            } else { // 사과 있음 -> 사과 먹어서 없애버리기
                board[nx][ny] = 0;
            }
            deq.add(new Info(nx, ny));

            if (timeCnt == t) { // 방향 바꿀 시간~~
                if (d == 'D') { // 오른쪽
                    nowDir = (nowDir+1)%4;
                } else { // 왼쪽
                    nowDir = (nowDir+3)%4;
                }
                if (!direction.isEmpty()) {
                    directInfo = direction.poll();
                    t = directInfo.time;
                    d = directInfo.dir;
                }
            }
        }
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        K = Integer.parseInt(br.readLine());

        board = new int[N+1][N+1];

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());

            int row = Integer.parseInt(st.nextToken()); // 행
            int col = Integer.parseInt(st.nextToken()); // 열

            board[row][col] = 1; // 사과가 있는 곳
        }

        direction = new LinkedList<>();

        L = Integer.parseInt(br.readLine());

        for (int i = 0; i < L; i++) {
            st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            char d = st.nextToken().charAt(0);

            direction.add(new DirectInfo(t, d)); // 방향변환에 대한 정보 저장
        }
        game();
        bw.write(timeCnt + " ");
        bw.flush();
        bw.close();
    }
}

 

 

 

🧠 헤맸던 부분

• 벽에 닿거나 몸통에 닿았을 때 게임을 끝내기 위해서는 break 가 아닌 return 을 사용해야 한다. 👉 이걸로 1시간 이상은 잡아먹었다..
• 사과를 먹었으면 없애기 위해서 1을 0으로 바꿔야 한다.