[백준] 3190. 뱀 -JAVA

1. 문제

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

 

2. 풀이 과정

N x N이 BOARD가 주어졌을 때, 사과가 있는 영역(1)과 빈 영역(0)이 존재한다.

뱀은 (0,0)에서 오른쪽 방향을 보면서 시작한다. 그리고 뱀은 주어진 시간마다 왼쪽(L) 또는 오른쪽(D)로 방향을 튼다.

뱀은 자기가 바라보고 있는 방향으로 1초에 1칸 이동한다.

• 사과가 있는 영역으로 이동: 사과를 먹고, 몸의 길이는 1만큼 늘어난다.
• 빈 영역으로 이동: 몸의 길이는 늘어나지 않고 뱀이 이동만 한다.

만약 이동할 영역이 벽이거나, 자신 몸이라면 종료된다.

게임이 몇 초에 끝내는 지 계산하는 문제이다.

 

처음에는 DFS로 접근했었다.. DFS로 푸니깐 도저히 뱀이 길이가 늘어나는 성질이 구현이 안되서 다른 풀이 방법으로 접근했다.

 

문제 접근 방식

이 문제는 큐를 활용한 시뮬레이션 방식으로 문제를 해결할 수 있다.

1. 먼저, BOARD 각 영역의 상태를 정리해보자. 총 3가지로 구분할 수 있다.

• 0 = 빈 영역
• 1 = 사과가 있는 영역
• 2 = 뱀이 차지하고 있는 영역 

2. 큐를 활용

큐의 성질을 활용하면 뱀의 몸이 늘어나고, 이동하는 성질을 구현하기 매우 적합하다.

큐에 뱀이 현재 영역(좌표)들을 저장하여 관리한다.

 

2-1. 초기 세팅

• 뱀의 시작점은 (0, 0)이다.
• 방향은 북(0), 동(1), 남(2), 서(3)로 표현할 수 있다.
• 뱀이 초기에 바라보고 방향은 동쪽이다.
• 경과시간을 나타내는 변수 time을 0으로 초기화 한다.

static int d = 1; // 초기 동쪽
int time = 0;
// 머리 위치
int headX = 0;
int headY = 0;
Queue<Point> q = new LinkedList<>();
q.offer(new Point(headX, headY));
BOARD[0][0] = 2;

 

2-2. 무한 루프

• 무한루프를 통해 단계적으로 뱀을 이동시켜보고, 게임 종료조건을 따라 무한루프를 종료시켜보자.

 

2-2-1. 이동 영역 구하기

• 현재 방향을 기준으로 방향 백터를 사용하여 다음 이동 영역(nx, ny)를 구한다.
• 경과시간을 1씩 증가시킨다.

static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};

int nx = headX + dx[d];
int ny = headY + dy[d];
time++;

 

2-2-2. 다음 이동영역이 벽이거나, 뱀의 영역인 경우

• 루프를 종료한다.

if (nx < 0 || nx >= N || ny < 0 || ny >= N || BOARD[nx][ny] == 2) { // 벽이거나 몸통이 부딪힐 때
    break;
}

 

 

2-2-3. 다음 이동영역이 사과 또는 빈 영역인 경우

• 사과인 경우
  • 큐에 이동영역을 저장
  • 이동영역을 뱀의 영역으로 변경
• 빈 영역인 경우
  • 큐에서 꼬리 영역을 꺼낸다.
  • 꼬리 영역을 빈 영역으로 만들어 준다.
  • 큐에 이동영역을 저장
  • 이동영역을 뱀의 영역으로 변경

Point next = new Point(nx, ny);
if (BOARD[nx][ny] == 1) {
    BOARD[nx][ny] = 2;
    q.offer(next);
} else if (BOARD[nx][ny] == 0) {
    Point tail = q.poll();
    BOARD[tail.x][tail.y] = 0;
    BOARD[nx][ny] = 2;
    q.offer(next);
}

 

2-2-4. 뱀 회전

• direction은 Map 형태로, key=시간, value=방향
• 현재 시간이 Map에 key 형태로 존재한다면, value에 따라 뱀의 방향을 회전시킨다. 

if (direction.containsKey(time)) {
    if (direction.get(time) == 'L') {
        d = (d + 3) % 4;  // 왼쪽
    } else if (direction.get(time) == 'D') {
        d = (d + 1) % 4;  // 오른쪽
    }
}

 

2-2-5. 뱀 머리 위치 설정

• 다음 이동 영역이 뱀의 머리 위치가 된다.

headX = nx;
headY = ny;

 

경과시간(time)을 리턴하면 끝!

 

3. 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int N; // 보드 크기
    static int K; // 사과 개수
    static int L; // 뱀의 방향 변환 횟수

    // 북(0), 동(1), 남(2), 서(3)
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int d = 1; // 초기 동쪽

    static int[][] BOARD;
    static Map<Integer, Character> direction = new HashMap<>();

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        BOARD = new int[N][N];
        K = Integer.parseInt(br.readLine());

        for (int i = 0; i < K; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;
            BOARD[x][y] = 1; // 사과
        }

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

        for (int i = 0; i < L; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            char c = st.nextToken().charAt(0);
            direction.put(x, c);
        }

        int result = solve();

        bw.write(result + "\n");
        bw.flush();
        bw.close();
    }

    static int solve() {
        int time = 0;
        // 머리 위치
        int headX = 0;
        int headY = 0;
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(headX, headY));
        BOARD[0][0] = 2;

        while (true) {
            int nx = headX + dx[d];
            int ny = headY + dy[d];
            time++;

            if (nx < 0 || nx >= N || ny < 0 || ny >= N || BOARD[nx][ny] == 2) { // 벽이거나 몸통이 부딪힐 때
                break;
            }

            Point next = new Point(nx, ny);
            if (BOARD[nx][ny] == 1) {
                BOARD[nx][ny] = 2;
                q.offer(next);
            } else if (BOARD[nx][ny] == 0) {
                Point tail = q.poll();
                BOARD[tail.x][tail.y] = 0;
                BOARD[nx][ny] = 2;
                q.offer(next);
            }

            if (direction.containsKey(time)) {
                if (direction.get(time) == 'L') {
                    d = (d + 3) % 4;  // 왼쪽
                } else if (direction.get(time) == 'D') {
                    d = (d + 1) % 4;  // 오른쪽
                }
            }
            headX = nx;
            headY = ny;
        }
        return time;
    }

    static class Point {
        int x;
        int y;

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