3190 - 뱀 (Java)

박세건·2025년 3월 19일

알고리즘 문제 해결

목록 보기

24/50

BOJ 3190 뱀 문제 풀이 후기 🐍✨

이번 포스팅에서는 백준 3190번 "뱀" 문제를 DFS를 이용하여 해결했던 과정을 공유함.
뱀이 이동하면서 사과를 먹으면 몸이 늘어나고, 자신의 몸이나 벽에 부딪히면 게임이 종료되는 문제였음.
특정 초마다 주어지는 방향 전환 명령에 따라 뱀의 이동을 시뮬레이션하여 최대 이동 시간을 구하는 것이 목표였음.

문제 개요 📌

문제 설명:
- 격자판 위에서 뱀이 움직임
- 사과(1) 를 먹으면 몸이 늘어남
- 빈 공간(0) 은 아무 변화 없음
- 뱀의 몸(2) 과 부딪히거나 벽에 닿으면 게임 종료
- 방향 전환 명령이 초 단위로 주어짐
목표:
- 뱀이 이동할 수 있는 최대 시간(초)를 구하는 것

접근 방법 및 핵심 아이디어 🚀

문제를 해결하기 위해 DFS (재귀적 시뮬레이션)를 사용하여 매 초마다 뱀의 상태를 업데이트함.
주요 아이디어는 아래와 같음:

맵 상태 관리 🗺️
- map 배열로 격자 상태를 관리함
  - 0: 빈 공간
  - 1: 사과 🍎
  - 2: 뱀의 몸 🐍
뱀의 몸 추적 🔍
- 뱀은 머리부터 꼬리까지 연결된 체인 형태
- 꼬리가 이동할 방향은 현재 방향과 다를 수 있으므로,
  각 몸의 좌표마다 다음 이동 좌표를 저장하는 nextBody 배열을 활용함
DFS 시뮬레이션 ⏱️
- moveDfs 함수를 재귀 호출하여,
  - 머리의 좌표와 꼬리의 좌표,
  - 현재 이동 방향, 그리고
  - 현재 시간(초)를 업데이트함
- 종료 조건:
  - 머리 좌표가 벽을 벗어나거나
  - 머리가 자신의 몸에 닿을 때
방향 전환 명령 처리 🔀
- Queue에 저장된 [초, 방향 전환 명령]을 체크하여,
  시간이 해당 명령과 일치하면 뱀의 이동 방향을 변경함
  - 0: 왼쪽 회전
  - 1: 오른쪽 회전

코드 설명 💻

아래는 주요 코드 부분에 대한 설명임:

1. 초기 설정 및 입력 처리 📥

맵 초기화:
- N×N 격자, 사과(1) 위치 설정
nextBody 배열:
- 각 좌표에서 다음 이동할 몸의 좌표를 저장 (꼬리 이동 추적)
방향 전환 명령:
- Queue에 [이동 시간(초), 방향 전환 (0: 왼쪽, 1: 오른쪽)]를 저장

2. DFS를 통한 뱀 이동 시뮬레이션 🏃‍♂️

private static int moveDfs(int hx, int hy, int tx, int ty, int curDir, int time) {
    // ⏰ 시간에 맞춰 방향 전환 처리
    if (queue.size() > 0 && queue.peek()[0] == time) {
        int nextDir = queue.poll()[1];
        if (nextDir == 0) curDir = (curDir - 1 + 4) % 4;
        else curDir = (curDir + 1) % 4;
    }
    // ➡️ 새로운 머리 좌표 계산
    int nhx = hx + dir[curDir][0];
    int nhy = hy + dir[curDir][1];
    // 🚧 벽에 부딪히면 종료
    if (nhx < 0 || nhx >= N || nhy < 0 || nhy >= N) {
        return time;
    }
    // ❌ 자기 몸에 부딪히면 종료
    if (map[nhx][nhy] == 2) {
        return time;
    }
    // 📍 현재 머리 위치에서 다음 몸의 좌표 갱신 (꼬리 이동 추적)
    nextBody[hx][hy][0] = nhx;
    nextBody[hx][hy][1] = nhy;
    int ntx = tx;
    int nty = ty;
    // 🍏 사과가 없으면 꼬리 이동: 꼬리 위치를 빈칸(0)으로 만들고, 다음 꼬리 좌표 갱신
    if (map[nhx][nhy] != 1) {
        map[tx][ty] = 0;
        ntx = nextBody[tx][ty][0];
        nty = nextBody[tx][ty][1];
    }
    // 🐍 새로운 머리 좌표에 뱀 몸 표시
    map[nhx][nhy] = 2;
    // ▶️ 다음 초로 재귀 호출 (시간 1 증가)
    return moveDfs(nhx, nhy, ntx, nty, curDir, time + 1);
}

머리 이동:
- 현재 방향에 따라 새로운 머리 좌표를 계산하고, 범위 및 충돌을 검사함.
꼬리 이동:
- 사과가 없는 경우, 꼬리 좌표를 nextBody 배열로 갱신하며 꼬리 위치를 업데이트함.
재귀 호출:
- 매 초마다 시간(time)을 증가시키며, DFS로 계속 진행함.

3. 최종 결과 출력 🎉

getAnswer() 함수에서 재귀 호출을 시작하여,
게임 종료 시까지의 최대 이동 시간을 구한 뒤 출력함.

최종 코드 📝

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static StringTokenizer st;
    private static StringBuilder sb = new StringBuilder();
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static int N, K, L;
    private static int[][] map; // 사과: 1, 뱀 몸: 2, 빈 공간: 0
    private static Queue<int[]> queue = new ArrayDeque<>(); // [이동 시간(초), 방향 전환: 0(왼쪽), 1(오른쪽)]
    private static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private static int[][][] nextBody; // 각 몸통 위치의 다음 좌표 저장

    public static void main(String[] args) throws IOException {
        inputSetting();
        map[0][0] = 2; // 시작 위치 (머리) 표시
        System.out.println(getAnswer());
    }

    private static int getAnswer() {
        // 초기 상태: (머리 좌표: 0,0), (꼬리 좌표: 0,0), 현재 방향: 1 (오른쪽), 시간: 1
        return moveDfs(0, 0, 0, 0, 1, 1);
    }

    private static int moveDfs(int hx, int hy, int tx, int ty, int curDir, int time) {
        // ⏰ 시간에 맞춰 방향 전환 처리
        if (queue.size() > 0 && queue.peek()[0] == time) {
            int nextDir = queue.poll()[1];
            if (nextDir == 0) curDir = (curDir - 1 + 4) % 4;
            else curDir = (curDir + 1) % 4;
        }
        // ➡️ 새로운 머리 좌표 계산
        int nhx = hx + dir[curDir][0];
        int nhy = hy + dir[curDir][1];
        // 🚧 벽에 부딪히면 종료
        if (nhx < 0 || nhx >= N || nhy < 0 || nhy >= N) {
            return time;
        }
        // ❌ 자기 몸에 부딪히면 종료
        if (map[nhx][nhy] == 2) {
            return time;
        }
        // 📍 현재 머리 위치에서 다음 몸의 좌표 갱신 (꼬리 이동 추적)
        nextBody[hx][hy][0] = nhx;
        nextBody[hx][hy][1] = nhy;
        int ntx = tx;
        int nty = ty;
        // 🍏 사과가 없으면 꼬리 이동: 꼬리 위치를 빈칸(0)으로 만들고, 다음 꼬리 좌표 갱신
        if (map[nhx][nhy] != 1) {
            map[tx][ty] = 0;
            ntx = nextBody[tx][ty][0];
            nty = nextBody[tx][ty][1];
        }
        // 🐍 새 머리 좌표에 뱀 몸 표시
        map[nhx][nhy] = 2;
        // ▶️ 다음 초로 재귀 호출 (시간 1 증가)
        return moveDfs(nhx, nhy, ntx, nty, curDir, time + 1);
    }

    private static void inputSetting() throws IOException {
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        nextBody = new int[N][N][2];
        K = Integer.parseInt(br.readLine());
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int ax = Integer.parseInt(st.nextToken()) - 1;
            int ay = Integer.parseInt(st.nextToken()) - 1;
            map[ax][ay] = 1;
        }
        L = Integer.parseInt(br.readLine());
        for (int i = 0; i < L; i++) {
            st = new StringTokenizer(br.readLine());
            int second = Integer.parseInt(st.nextToken());
            int nextMove = (st.nextToken().equals("D")) ? 1 : 0;
            queue.add(new int[]{second, nextMove});
        }
    }
}

결론 🎯

개선한 점 🛠️

뱀 몸 추적:
- nextBody 배열을 통해 각 몸통의 다음 이동 좌표를 저장하여 꼬리 이동을 정확하게 추적함.
재귀적 시뮬레이션:
- DFS를 활용하여 매 초마다 뱀의 상태(머리, 꼬리, 방향, 시간)를 업데이트하고, 종료 조건(벽 충돌, 자기 충돌)을 정확하게 체크함.
방향 전환 처리:
- 주어진 시간에 맞춰 방향 전환 명령을 큐에서 꺼내어 처리함으로써 게임의 흐름을 올바르게 시뮬레이션함.