[BOJ/Java] 3190. 뱀

[BOJ/Java] 3190. 뱀

3190번: 뱀

---

문제 해석

이 게임에서 뱀은 격자 상에서 사과를 먹으며 이동하고, 자신의 몸이나 벽에 부딪히면 게임이 종료된다. 뱀은 처음에 오른쪽을 향하며, 일정 시간마다 방향 전환 명령을 받는다. 이 문제는 뱀이 사과를 먹거나 몸을 길게 하면서 주어진 명령에 따라 어떻게 움직이는지를 시뮬레이션해야 한다.

풀이 과정

이 Java 코드는 뱀의 움직임을 시뮬레이션하여 게임이 언제 종료되는지를 결정한다. 뱀의 머리 위치를 따라 움직이면서, 몸통을 나타내는 배열을 업데이트 한다.

 

1. 입력 처리: 격자의 크기와 사과의 위치를 입력받는다. 방향 전환 명령도 입력받아 저장한다.
2. 뱀의 이동: 격자 내에서 뱀의 머리를 이동시키고, 각 시간마다 방향 전환 여부를 확인한다.
3. 사과의 여부: 뱀의 머리가 사과에 도달하면 몸길이를 늘리고, 사과가 없는 경우 몸길이를 유지하면서 뱀의 꼬리를 줄인다.
4. 게임 종료 조건: 뱀의 머리가 격자의 범위를 벗어나거나, 자신의 몸통에 부딪히면 게임이 종료된다.

코드

package edu.ssafy.im.BOJ.Gold.G4.No3190;

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static int N, K, L;
    private static int[][] map;
    private static int[] X;
    private static char[] C;
    private static int[] dx = {0, 1, 0, -1};
    private static int[] dy = {1, 0, -1, 0};
    private static int ans;
    private static int[][] navigation;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        N = Integer.parseInt(br.readLine()); // 격자 크기
        K = Integer.parseInt(br.readLine()); // 사과 개수
        map = new int[N][N];

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

        L = Integer.parseInt(br.readLine()); // 방향 전환 횟수
        X = new int[L];
        C = new char[L];
        for (int i = 0; i < L; i++) {
            st = new StringTokenizer(br.readLine());
            X[i] = Integer.parseInt(st.nextToken());
            C[i] = st.nextToken().charAt(0); // 방향 전환 정보
        }

        sol(); // 시뮬레이션 실행
        sb.append(ans+1); // 마지막으로 이동 성공한 다음 턴을 추가
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static void sol() {
        int d = 0, idx = 0; // 초기 방향 및 방향 전환 인덱스
        ans = 0;
        int headX = 0, headY = 0; // 뱀의 머리 위치
        int tailX = 0, tailY = 0; // 뱀의 꼬리 위치
        navigation = new int[N][N]; // 뱀의 이동 방향을 기록
        map[headX][headY] = 2; // 뱀의 초기 위치
        while (true) {
            if (idx < X.length) {
                if (X[idx] == ans) { // 방향 전환 시점
                    if(C[idx] == 'L') {
                        d = d - 1 == -1 ? 3 : d - 1; // 왼쪽으로 회전
                    } else if(C[idx] == 'D') {
                        d = d + 1 == 4 ? 0 : d + 1; // 오른쪽으로 회전
                    }
                    idx++;
                }
                navigation[headX][headY] = d;
            }

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

            if (nx < 0 || ny < 0 || nx >= N || ny >= N) break; // 벽에 부딪힘
            if (map[nx][ny] == 2) break; // 자기 몸에 부딪힘

            if (map[nx][ny] != 1) { // 사과가 없는 경우 꼬리 이동
                map[tailX][tailY] = 0;
                int ntx = tailX + dx[navigation[tailX][tailY]];
                int nty = tailY + dy[navigation[tailX][tailY]];
                tailX = ntx;
                tailY = nty;
            }

            headX = nx;
            headY = ny;
            map[headX][headY] = 2; // 머리를 새 위치로 이동
            ans++; // 시간 증가
        }
    }
}

시간 복잡도 분석

시간 복잡도는 𝑂(𝑁^2), 뱀이 이동하는 동안 격자 내 모든 칸을 점유할 수 있으며, 방향 전환 및 위치 갱신에 대해 선형적으로 처리한다.

느낀점

이 문제는 격자와 시뮬레이션 기반의 문제 해결 방법을 실습하는 좋은 기회였다. 뱀 게임의 로직을 구현하면서 방향 전환, 머리와 꼬리의 관리 등 여러 조건을 세심하게 처리해야 했다. 이 과정에서 자료구조의 선택과 알고리즘의 효율성에 대해 깊이 고민할 수 있었다.