백준 3190: 뱀 - 구현, 큐 (파이썬)

뱀 성공다국어

3190번: 뱀

문제

'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

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

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

입력

첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)

다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.

다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)

다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데, 정수 X와 문자 C로 이루어져 있으며. 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.

출력

첫째 줄에 게임이 몇 초에 끝나는지 출력한다.

 

내 코드

import sys

#몸끼리 충돌했는지 여부를 리턴하는 함수.
def isOk(nx,ny):
    #전체 몸에서 현재 머리랑 같은 부분이 있으면 충돌한 것임
    if [nx,ny] in body[1:]:
        return False
    return True


#방향에 맞는 회전 후 현재 방향 dir을 최신화하는 함수.
def turn(x):
    global dir

    #현재 방향에 따라 커맨드 수행 시 방향이 달라진다.(2*4가지)
    if dir==0 and x=='L':
        dir=3
    elif dir==0 and x=='D':
        dir=1
    elif dir==1 and x=='L':
        dir=0
    elif dir==1 and x=='D':
        dir=2
    elif dir==2 and x=='L':
        dir=1
    elif dir==2 and x=='D':
        dir=3
    elif dir==3 and x=='L':
        dir=2
    elif dir==3 and x=='D':
        dir=0


def move(d):
    #현재 방향에 따라 전진 시 좌표 변동이 다르다 (4가지)
    if d==0: #위
        nx=body[0][0]-1
        ny=body[0][1]
    elif d==1: #오른쪽
        nx=body[0][0]
        ny=body[0][1]+1
    elif d==2: #아래
        nx=body[0][0]+1
        ny=body[0][1]
    elif d==3: #왼쪽
        nx=body[0][0]
        ny=body[0][1]-1
    
    #좌표 범위 밖으로 나가면 게임 종료. return False;
    if nx<0 or nx>=n or ny<0 or ny>=n:
        return False
    
    
    if arr[nx][ny]==1: #전진한 위치가 사과가 있는 곳이면,
        body.insert(0,[nx,ny]) #맨 앞에 머리 추가하고,
        arr[nx][ny]=0 #사과를 먹은 상태로 돌림 (0)
        return isOk(nx,ny) #충돌했는지 여부 체크.
    

    #전진한 위치가 사과아 있는 곳이 아니면,
    body.insert(0,[nx,ny]) #맨 앞에 머리 추가하고,
    if isOk(nx,ny): #충돌 하지 않았으면,
        body.pop() #꼬리 자르기
        return True
    else: #충돌 했으면 return False;
        return False
 


#메인 코드 부분
n=int(sys.stdin.readline())
k=int(sys.stdin.readline())

arr=[[0]*n for _ in range(n)] #전체 지도를 0 초기화.


#사과 있는 곳을 1로 처리.
for _ in range(k):
    apple_x,apple_y=map(int,sys.stdin.readline().split())
    arr[apple_x-1][apple_y-1]=1


#명령어들을 딕셔너리 형태로 저장.
command={}
l=int(sys.stdin.readline())
for _ in range(l):
    tmp=list(sys.stdin.readline().rstrip().split())
    command[int(tmp[0])]=tmp[1]


body=[[0,0]] #전체 몸을 관리. 처음에는 (0,0) 위치에 머리만 존재.
dir=1 #초기 방향은 오른쪽(1) *0:위, 1:오른쪽, 2:아래, 3:왼쪽
timer=0
while True:
    timer+=1 #시간이 흐른다

    isContinue=move(dir) #전진. 전진 후 게임 오버 조건인지 아닌지 리턴함.
    if not isContinue: #게임 오버 조건이면,
        break #break;

    if timer in command: #특정 시간대의 회전 명령이 있으면,
        turn(command[timer]) #회전 명령 수행

print(timer)

 

풀이 및 접근)

- 처음에는 뱀의 모든 이동을 실제 시뮬레이션을 하려고 했다. 그러다보니 코너를 도는 것에 너무 많은 것이 요구됐었다. 몸의 특정 구간들마다 이동하는 방향이 각각 다른 상황들이 일어나기 때문이다.

- 문제의 힌트를 보고 방법을 깨달았다. 전진하는 것을 그저 머리 부분만 새로 추가하고 꼬리 부분을 제거하면 그것이 전진과 같은 상황인 것이다.

- 일반 전진은 위에서 말한 것과 같이 머리부분 추가+꼬리부분 제거이지만, 사과를 먹었을 시에는 머리부분 추가만 이루어진다. 사과를 먹어 몸의 길이가 길어졌으므로 꼬리를 제거할 필요가 없다.

- 게임이 종료되는 조건은 머리 부분이 좌표 범위 밖을 벗어나거나, 머리 부분이 자신의 몸 부분과 겹치는 부분이 있을 때이다.

- 이에 대한 조건들을 코드의 주석을 통해 자세히 적어 놓았다.

- 가장 중요한 점들을 요약하면,

    -현재 방향 상태에 따라 전진 방향이 달라진다

    -현재 방향에 따라 커맨드명령에 의해 방향이 달라진다 (2*4 가지)

    -자신의 몸과 충돌하는 부분에서, 머리만 전진시키고 자신의 몸을 비교하여야 한다. 아직 머리 이외의 몸은 움직이지 않은 상태로 비교해야 한다.

 

 

자바 ver.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.*;


public class Main {
    static int dir=1;
    static int[][] arr;
    static int k;
    static List<int[]> body=new ArrayList<>();
    static int timer;
    static int n;

    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        n=Integer.parseInt(br.readLine());
        k=Integer.parseInt(br.readLine());

        arr=new int[n][n];
        for(int i=0; i<n; i++)
            Arrays.fill(arr[i],0);

        for(int i=0; i<k; i++){
            String[] s = br.readLine().split(" ");
            int x=Integer.parseInt(s[0]);
            int y=Integer.parseInt(s[1]);
            arr[x-1][y-1]=1;
        }


        Map<Integer,String> command=new HashMap<>();
        int l=Integer.parseInt(br.readLine());
        for(int i=0; i<l; i++){
            String[] s = br.readLine().split(" ");
            command.put(Integer.parseInt(s[0]),s[1]);
        }

        body.add(new int[]{0,0});

        timer=0;

        while(true){
            timer++;

            boolean isContinue=move(dir);
            if(!isContinue){
                break;
            }

            if(command.containsKey(timer)){
                turn(command.get(timer));
            }

        }

        System.out.println(timer);

    } //end of main method


    public static boolean move(int d){
        int nx=0;
        int ny=0;

        if (d == 0) {
            nx=body.get(0)[0]-1;
            ny=body.get(0)[1];
        }
        else if(d==1){
            nx=body.get(0)[0];
            ny=body.get(0)[1]+1;
        }
        else if(d==2){
            nx=body.get(0)[0]+1;
            ny=body.get(0)[1];
        }
        else if(d==3){
            nx=body.get(0)[0];
            ny=body.get(0)[1]-1;
        }

        if(nx<0||nx>=n||ny<0||ny>=n){
            return false;
        }

        if(arr[nx][ny]==1){
            body.add(0,new int[]{nx,ny});
            arr[nx][ny]=0;
            return isOk(nx,ny);
        }

        body.add(0,new int[]{nx,ny});
        if(isOk(nx,ny)){
            body.remove(body.size()-1);
            return true;
        }
        else{
            return false;
        }

    }

    public static boolean isOk(int nx, int ny){
        for(int i=1; i<body.size(); i++){
            if(body.get(i)[0]==nx && body.get(i)[1]==ny){
                return false;
            }
        }
        return true;
    }

    public static void turn(String x){
        if(dir==0 && x.equals("L")){
            dir=3;
        }
        else if(dir==0 && x.equals("D")){
            dir=1;
        }
        else if(dir==1 && x.equals("L")){
            dir=0;
        }
        else if(dir==1 && x.equals("D")){
            dir=2;
        }
        else if(dir==2 && x.equals("L")){
            dir=1;
        }
        else if(dir==2 && x.equals("D")){
            dir=3;
        }
        else if(dir==3 && x.equals("L")){
            dir=2;
        }
        else if(dir==3 && x.equals("D")){
            dir=0;
        }

    }

} //end of Main class