[백준] 알고리즘 분류(구현,JAVA)3190번, 뱀

문제 링크

3190번: 뱀

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 게임이 시작할 때 뱀은 (1, 1)에서 시작하며 오른쪽으로 이동합니다.

2. 뱀의 머리가 벽이나 자기자신과 부딪히면 게임이 종료됩니다.

3. 뱀이 사과를 먹으면 몸길이가 증가합니다.

4. 뱀은 L개의 주어진 방향에 따라 방향 전환을 진행합니다.

5. 뱀이 움직이면서 게임이 종료되는 초를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. Dummy 도스게임에서 뱀이 움직이는 시뮬레이션을 진행합니다.

 

3. 게임이 종료되었을 때 초를 결과로 출력합니다.

 

 

시뮬레이션.

 

저는 Queue를 이용해서 현재 뱀의 정보를 저장하였습니다.

 

※Queue는 FIFO이기 때문에 뱀의 길이가 증가하였을 때에도 뱀의 머리부터 이동이 가능하기 때문입니다.

 

뱀이 이동할 때 상황

 

※보드의 상황을 board[][]에 저장하였습니다.

 

0 : 빈공간, 1 : 뱀, 2 : 사과

 

 

벽이나 자기자신을 부딪힐 때

 

: 뱀이 이동하려는 칸이 board[i][j] == 1 이거나 board 범위를 벗어날 때

 

: 게임 종료!

 

 

사과를 먹을 때

 

: 뱀의 머리가 이동할 때 board[i][j] == 2일 때

 

: 사과를 먹었기 때문에 뱀의 꼬리에서 몸길이 증가!

 

 

 

빈 공간을 이동할 때

 

: 뱀의 머리가 이동할 때 board[i][j] == 0일 때

 

: 몸길이 증가하지 않고 그대로 이동!

 

 

시뮬레이션이 진행되는 과정은 예제입력으로 확인하실 수 있습니다.

 

예제입력 3.

 

1. 입력된 정보를 저장합니다.

 

N : 10
K : 5

L : 4

 

방향 전환

8 D
10 D
11 D
13 L

 

Board

 

1	2	2		2	2	2

 

2. Dummy 도스게임에서 뱀이 움직이는 시뮬레이션을 진행합니다.

 

시뮬레이션 진행!

★ : 머리표시

1(→)	1(→) ★	2		2	2	2

 

....8초까지 → 이동

			1(→)	1(→)	1(→)	1(→)	1(→)	1(↓) ★

8초이후 'D'로 방향 전환 → ▶ ↓

 

....10초까지 ↓ 이동

					1(→)	1(→)	1(→)	1(↓)
								1(↓)
								1(←) ★

10초이후 'D'로 방향 전환 ↓ ▶ ←

 

11초 이동!

						1(→)	1(→)	1(↓)
								1(↓)
							1(←) ★	1(←)

11초이후 'D'로 방향 전환 ← ▶ ↑

 

...13초 이동시!

							1(→)	1(↓)
							1(↑) ★	1(↓)
							1(↑)	1(←)

13초에 이동할 때 자기 자신가 부딪히기 때문에 게임 종료!

 

3. 게임이 종료되었을 때 초를 결과로 출력합니다.

 

게임 종료할 때 시간 : 13초

13을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 뱀 게임에 대한 정보를 띄어쓰기 기준 나누었습니다.
• 뱀의 초기위치(1, 1)를 Board와 Queue에 반영되도록 합니다.
• gameStart를 이용하여 뱀 게임에 대한 시뮬레이션을 진행합니다.
• 시뮬레이션 종료한 뒤, 진행된 시간을 결과로  BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• startGame함수는 뱀 게임에서 뱀이 이동하는 것에 대한 시뮬레이션을 진행합니다.
• inSpace함수는 뱀이 이동할 때 벽에 부딪히는지 확인합니다.

 

결과코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{
    //뱀 관련 정보 클래스
    static class snake{
        //move : 이동한 횟수, y : y축 위치, x : x축 위치, d : 다음 이동 방향
        int move, y, x, d;
        //생성자
        public snake( int move, int y, int x, int d){
            this.move = move;
            this.y = y;
            this.x = x;
            this.d = d;
        }
    }
    static int[][] board;	//게임 보드 정보 배열
    static int[] dy = {-1, 0, 1, 0};	//상우하좌 y변경값
    static int[] dx = {0, 1, 0, -1};	//상우하좌 x변경값
    static int[] directions = new int[10001];	//방향 변경 저장 배열
    static Queue<snake> snakes = new LinkedList<>();	//뱀의 정보 저장 Queue
    static int N;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        int K = Integer.parseInt(br.readLine());
        StringTokenizer st;
        board = new int[N+1][N+1];
        //사과 정보 Board 배열에 저장!
        for(int i=0;i<K;i++){
            st = new StringTokenizer(br.readLine()," ");
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            board[y][x] = 2;	//사과 : 2
        }
        int L = Integer.parseInt(br.readLine());
        //방향전환 정보 저장
        for(int i=0;i<L;i++){
            st = new StringTokenizer(br.readLine()," ");
            int X = Integer.parseInt(st.nextToken());
            String C = st.nextToken();
            if(C.equals("L"))	//왼쪽(L) : 1
                directions[X] = 1;
            else		//오른쪽(D) : 2
                directions[X] = 2;
        }
        //초기 뱀의 위치 저장
        snakes.add(new snake(0,1, 1, 1));
        board[1][1] = 1;	//초기 뱀의 위치 Board에 반영
        int answer = gameStart();	//시뮬레이션 진행!
        bw.write(answer + "");	//진행된 초 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //뱀 게임 시뮬레이션 진행하는 함수
    static int gameStart(){
        //시뮬레이션 진행!
        while(true){
            int size = snakes.size();	//현재 뱀의 길이 저장
            boolean eating = false;		//사과 먹는지 확인 변수
            //뱀 이동 진행!
            for(int i=0;i<size;i++){
                snake cur = snakes.poll();
                board[cur.y][cur.x] = 0;
                //이동방향에 맞게 이동!
                int tempX = cur.x + dx[cur.d];
                int tempY = cur.y + dy[cur.d];
                //벽이나 자기자신과 부딪힐 때
                if(!inSpace(tempY, tempX) || board[tempY][tempX] == 1)
                    return cur.move + 1;	//게임 종료!
                else{		//뱀이 이동을 성공하였을 때
                    int tempM = cur.move+1;	//이동 + 1
                    int tempD = cur.d;	//방향 저장
                    if(directions[tempM] == 2)	//'D'로 방향전환 일어날 때
                        tempD = cur.d+1 == 4? 0 : cur.d+1;
                    else if(directions[tempM] == 1)	//'L'로 방향전환 일어날 때
                        tempD = cur.d-1 == -1? 3 : cur.d-1;
                    //이동한 뱀의 정보 Queue 저장
                    snakes.add(new snake(tempM, tempY,tempX, tempD));
                    //뱀의 머리가 사과를 먹었을 때
                    if(i == 0 && board[tempY][tempX] == 2)
                        eating = true;
                    //사과를 먹었을 때 뱀의 꼬리는 이동 및 현재 위치도 추가!
                    if(i == size-1 && eating){
                        board[cur.y][cur.x] = 1;
                        snakes.add(cur);	//현재 위치 추가
                    }
                    board[tempY][tempX] = 1;	//뱀 이동한 공간 Board에 반영
                }
            }
        }
    }
    //공간에 존재하는지 확인 함수(벽에 부딪히는지 확인)
    static boolean inSpace(int y, int x){
        if(y > 0 && y<=N && x>0 && x<=N)	//벽에 부딪히지 않을 때
            return true;
        return false;	//벽에 부딪힐 때
    }
}