[문제 풀이] 백준 3190번 뱀 JAVA

문제

  문제접근 방법   

해당 문제는 N x N 크기의 정사각 보드가 존재하고 해당 보드 위에 사과가  몇몇 칸에 놓여 있다고 할 때 뱀이 아래의 규칙에 맞춰 움직이다가 종료 조건에 의해서 종료되는 게임이 있다. 이때 게임이 몇 초에 종료되는지를 출력하는 문제이다.

먼저 뱀이 움직이는 규칙과 종료 조건은 아래와 같다. 게임은 아래 순서대로 진행된다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

문제를 읽자마자 구현 문제라는 것을 알게 되었고 문제를 분석해 본 결과 아래와 같은 조건에 유념해 코드를 작성해 보기로 하였다.

• 머리의 위치와 꼬리의 위치를 관리할 배열 필요
• 회전을 관리하는 변수 필요
• 시간을 카운트하는 변수 필요
• 사과의 위치를 저장할 배열 필요

처음에는 위의 조건들만가지고 아래처럼 코드를 작성하였다.

< 초기 코드  >

import java.util.*;
//방향 전환되면 반대로간다고 생각한 ver
public class Main{
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int n=s.nextInt();
        int k=s.nextInt();
        int len=1;
        int time=0;
        int head[]=new int[]{1,1};
        int tail[]=new int[]{1,1};
        char direction='D';
        int statusD=1;
        int rotateN=1; //1 ,2, 3, 4로 구분 진행
        
        int map[][]=new int[n+1][n+1];
        char move[]=new char[10_001];
        for(int i=0;i<k;i++){
            int x=s.nextInt();
            int y=s.nextInt();
            map[x][y]=1;
        } //사과가 존재한다 == 1로 표시
        
        
        int l=s.nextInt();
        for(int i=0;i<l;i++){
            int t=s.nextInt();
            move[t]=s.next().charAt(0);
        }
        
        
        while(true){
            if(move[time]=='D'||move[time]=='L'){
                if(move[time]=='D'){
                    rotateN=(rotateN+1)%4;
                    direction='D';
                    statusD=Math.abs(statusD);
                }
                else{
                    rotateN=(rotateN-1+4)%4;
                    direction='L';
                    statusD=statusD*(-1);
                }
            }
            time++;
            switch(rotateN){
                case 1:
                    head[1]+=statusD;
                    break;
                case 2:
                    head[0]+=statusD;
                    break;
                case 3:
                    head[1]+=(-1*statusD);
                    break;
                case 4:
                    head[0]+=(-1*statusD);
                    break;  
            }
            if(len!=1&&((head[0]==head[1]&&tail[0]==tail[1])||head[0]<=0||head[0]>n||head[1]<=0||head[1]>n)) break;
            if(map[head[0]][head[1]]!=1){
                switch(rotateN){
                    case 1:
                        tail[1]+=statusD;
                        break;
                    case 2:
                        tail[0]+=statusD;
                        break;
                    case 3:
                        tail[1]+=(-1*statusD);
                        break;
                    case 4:
                        tail[0]+=(-1*statusD);
                        break;  
                }
            }
            else{len++;}
            if(len!=1&&((head[0]==head[1]&&tail[0]==tail[1])||head[0]<=0||head[0]>n||head[1]<=0||head[1]>n)) break;
            
            
            
        }
        System.out.println(time);
    }
}

처음에 조건을 읽고나서 왼쪽 오른쪽 방향으로 회전하면서 움직여야 할 방향도 왼쪽 오른쪽으로 바뀌나 보다고 생각하고 문제를 풀이하였다.  하지만 뱀의 머리 방향이 회전하고 회전된 방향으로 한 칸씩 이동하는 것이어서 아래와 같이 코드를 수정하였다.

또 direction 을 1부터 시작하고 증가시킨 후 4로 나누어주는 방식은 4일 경우에 나머지가 0이 되는 경우가 발생해 잘못된 이동을 보여주게 되는 문제를 발견하였고 가장 마지막에 진행되어야 할 방향 전환 로직이 가장 상단에 나와 있는 문제도 존재해 이 부분 또한 수정해 주었다. 마지막으로 꼬리의 좌표를 추가해 주는 방식으로 코드를 작성하면 꼬리의 길이를 제대로 반영해주지 못하고 회전할 때 한 박자씩 늦게 반영되기 때문에 이 또한 문제가 발생할 수 있어 Queue를 통해 관리해 주는 방식으로 수정해 주었다.

< 최종 코드 >

import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        Queue<int[]> tail=new LinkedList<>();
        
        int n=s.nextInt();
        int k=s.nextInt();
        int time=0;
        boolean visited[][]=new boolean[n+1][n+1];
        boolean map[][]=new boolean[n+1][n+1];
        char move[]=new char[10_001];
        visited[1][1]=true;
        int head[]=new int[]{1,1};
        int direction=0; // 0,1,2,3 우 하 좌 상
        
        // 사과 위치 존재(true) 존해하지 않음(false)
        for(int i=0;i<k;i++){
            int x=s.nextInt();
            int y=s.nextInt();
            map[x][y]=true;
        }
        
        //뱀 방향 전환 지시 입력력
         int l=s.nextInt();
        for(int i=0;i<l;i++){
            int t=s.nextInt();
            move[t]=s.next().charAt(0);
        }
        
        tail.offer(new int[]{head[0],head[1]});
        while(true){

            time++;
            switch(direction){
                case 0:   // 오른쪽 방향
                    head[1]+=1;
                    break;
                case 1: // 아래쪽 방향
                    head[0]+=1;
                    break;
                case 2:// 왼쪽 방향
                    head[1]-=1;
                    break;
                case 3: // 위쪽 방향
                    head[0]-=1;
                    break;
            }
            tail.offer(new int[]{head[0],head[1]});
            
            if(head[1]<=0||head[0]<=0||head[1]>n||head[0]>n)break; //벽에 충돌하는 경우
            
            
            
            
            // 뱀이 본인 몸통과 충돌하는 경우
            if(visited[head[0]][head[1]]){
                break;
            }
            if(!map[head[0]][head[1]]){
                int xy[]=tail.poll();
                visited[xy[0]][xy[1]]=false;
            }else{
                map[head[0]][head[1]]=false;
            }
            visited[head[0]][head[1]]=true;
            
            // 뱀 방향 전환 지시시
            if(move[time]=='D'||move[time]=='L'){
                if(move[time]=='D'){
                    direction=(direction+1)%4;
                }
                else{
                    direction=(direction-1+4)%4;
                }
            }
            
        
        }
        System.out.println(time);
    }
}

수정한 결과 맞았다는 결과를 받았고 코드에 대해서 간단하게 설명하도록 하겠다.

먼저 뱀의 머리와 꼬리 위치를 저장해 주는 배열과 큐를 각각 선언해 주었고

뱀의 꼬리의 길이를 매번 측정하고 이를 기반으로 몸통과의 충돌여부를 판단해 주는 것은 매우 비효율적이라 판단해서

뱀이 방문해 있는 곳을 따로 관리해 주는 visited배열을 선언해 주었다. 

또 뱀의 머리가 어느 방향을 향하는지를 의미하는 direction 변수를 선언해 머리가 회전했을 때 이동하는 방향을 저장해 주었다.

그리고 move 배열을 통해서 방향 지시 입력을 저장해 주었고 

마지막으로 사과의 위치를 저장하는 map배열을 선언하는 것으로 코드 초기 세팅을 마치었다.

이후 while문부터가 뱀의 이동과 회전을 담당하는 부분인데 먼저 방향이 어느 방향인지에 따라서 이동을 진행한다. 

이동진행한 칸이 벽인지 아닌지 확인하고  본인 몸과도 충돌하지 않는다면 사과가 존재하는지 안 하는지를 판단해

사과가 있다면 몸의 길이가 늘어나므로 꼬리를 현재 좌표에 유지하고

사과가 존재하지 않는다면 길이가 원상태로 와야 하므로 좌표를 한 칸 앞으로 이동해 주는 식으로 코드를 작성하였다.

이후 마지막에 move가 D이거나 L이면 회전시켜주고 몸통 혹은 벽과 충돌 시 종료되게 구현하였다.

 

  마무리  

해당 문제는 아이디어와 방향은 어렵지 않게 떠올렸지만 세부적으로 신경 쓸게 많았다. 예를 들어 사과 있는 칸에 도착하면

뱀이 사과를 먹었기 때문에 해당칸의 사과를 제거해 주는 과정을 거쳐야 하는데 이를 고려하지 못한 경우도 있었고 

몸과 충돌하는 경우, 벽과 충돌하는 경우를 어디에 작성할지도 고려해야 했다. 이처럼 많은 것들을 고려해야 했고 그 때문에 어렵게 느껴졌다. 조금 더 많은 구현 문제들을 풀이하고 경험해 봐야 더 쉽게 떠올리고 풀이할 수 있을 것이라고 생각했다.

  추가 코드 분석 및 풀이  

 

 

< 추가 코드 ver BigInteger + gcd 메서드 >

 

 

 참고 자료