백준 알고리즘[큐] 3190 - 뱀

https://www.acmicpc.net/problem/3190

    import java.io.FileInputStream;
    import java.io.FileNotFoundException;
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    
    public class Main {
        public static int[][] maps;
        public static char[] moveDirectMaps;
        public static int[] moveSecMaps;
        public static int n,k,l,sec;
        public static Queue<Integer> xQueue, yQueue;
        
        public static void main(String[] args) throws FileNotFoundException {
            FileInputStream fi = new FileInputStream("C:\\Users\\SeonMi\\Desktop\\JavaTools\\Tools\\workspace\\Solution\\src\\data.txt");
            //Scanner sc = new Scanner(System.in);
            Scanner sc = new Scanner(fi);
            
            n = sc.nextInt();
            maps = new int[101][101];
            moveDirectMaps = new char[101];
            moveSecMaps = new int[101];
            
            k = sc.nextInt();
            
            // maps 에서 0->사과x,  뱀x // 1-> 사과 // 2-> 뱀
            for(int i=0;i<k;i++){
                maps[sc.nextInt()][sc.nextInt()] = 1;
            }
            
            l=sc.nextInt();
            for(int j=1;j<l+1;j++){
                moveSecMaps[j] = sc.nextInt();
                moveDirectMaps[j] = sc.next().charAt(0);
            }
            
            // 1->L 2->U 3->R 4->D 
            int dir = 3;
            boolean isMove = true;
            int x=1, y=1;
            int moveIdx = 1;
            xQueue = new LinkedList<Integer>();
            yQueue = new LinkedList<Integer>();
            maps[1][1] = 2; // 뱀이 첫번째에 있음.
            enqueue(1,1);
            sec=0;
            
             while(true){
                sec++;
                /*for(int i=1;i<n+1;i++){
                    for(int j=1;j<n+1;j++){
                        System.out.print(maps[i][j]+" ");
                    }
                    System.out.println();
                }
                System.out.println("-----------------------");*/
                if(dir==1){ // L
                    isMove = checkMove(x, y,dir);
                    y--;
                }
                else if(dir==2){ // U
                    isMove = checkMove(x, y,dir);
                    x--;
                }
                else if(dir==3){ // R
                    isMove = checkMove(x, y,dir);
                    y++;
                }
                else{ // D
                    isMove = checkMove(x, y,dir);
                    x++;
                }
                
                if(!isMove) // 벽이나 뱀이 있으면
                    break;
                else{
                    enqueue(x, y); // 다음 칸에  큐 추가
                    if(maps[x][y]!=1){ // 사과가 없다면, 꼬리 부분(큐 제일 앞부분)을 없애주고, 뱀이 있던 표시 2->0 으로 없애준다.
                        maps[xQueue.poll()][yQueue.poll()] = 0; // 뱀이 있던 부분을 없애준다.
                    }
                    maps[x][y]=2; // 뱀이 있다고 표시함.
                }
 
                if(moveSecMaps[moveIdx]==sec){
                    dir = changeDirection(dir, moveDirectMaps[moveIdx]);
                    moveIdx++;
                }
            }
             System.out.println(sec);
        }
        
        public static int changeDirection(int _dir, char moveDirection){
            int dir = _dir;        
            if(moveDirection=='D'){
                if(dir!=4)
                    dir = _dir+1;
                else 
                    dir = 1;
            }
            else{
                if(dir!=1)
                    dir = _dir-1;
                else
                    dir = 4;
            }        
          return dir;
        }
        
        public static boolean checkMove(int x, int y, int dir){
            boolean check = false;
            if(dir==1){ // L
                if(y!=1){
                    if(maps[x][y-1]!=2)
                        check = true;
                }
            }
            else if(dir==2){ //U
                if(x!=1){
                    if(maps[x-1][y]!=2)
                        check = true;
                }            
            }
            else if(dir==3){ // R
                if(y!=n){
                    if(maps[x][y+1]!=2 )
                        check = true;
                }
            }
            else{
                if(x!=n){ // D
                    if(maps[x+1][y]!=2)
                        check = true;
                }
            }
            return check;
        }
        
        public static void enqueue(int _x, int _y){
            xQueue.add(_x);
            yQueue.add(_y);
        }
        
        
        
    }

풀이방법 :

maps는 (1,1)~(n,n)까지 존재, maps 배열에는 0(아무것도 없음), 1(사과), 2(뱀) 세 가지 상태가 존재한다.

초기화해주기

Queue에 뱀의 현재 위치(1,1) 넣어주고, 현재 위치에 뱀이 있다는 표시 maps[1][1]=2 를 해준다.

while문 시작

1.초 증가 

2.다음 벽에 뱀 존재 or 벽 존재 여부 검사  -> 존재하면 break;

존재하지 않는다면, 이동 가능하므로 Queue에 이동할 위치 저장, 현재 위치 증가해줌.

3.사과 존재 여부 검사 -> 존재하면 continue;

사과가 존재하지 않는다면,  큐의 가장 앞부분(가장 늦게 들어온 tail)을 Poll()해주고 tail 위치를 0으로 바꿔준다.(뱀이 없다는 표시)

4. 현재 위치에 뱀이 있음(maps[x][y]=2) 표시해준다.

 

5. 일정 시간 후 방향이 바뀌는지 여부 확인, 바뀐다면 방향을 바꿔준다.

큐 안쓰고 Head, Tail 로 푸는 경우

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
class Main {
    static int[][] maps;
 
    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(System.in);
        int answer = 0;
 
        int n = sc.nextInt();
        int k = sc.nextInt();
        maps = new int[101][101];
        for (int i = 0; i < k; i++) {
            maps[sc.nextInt()][sc.nextInt()] = 5; // 사과가 있는 위치는 1
        }
        maps[1][1] = 2; // 뱀이 있는 위치는 이동방향(1,2,3,4 로 표시)
 
        int l = sc.nextInt();
        String[] changeDir = new String[100];
        int[] changeDirTime = new int[100];
 
        for (int i = 0; i < l; i++) {
            changeDirTime[i] = sc.nextInt();
            changeDir[i] = sc.next();
        }
 
        // x, y, 방향 순으로 저장할 배열
        int[] tail = new int[3];
        int[] head = new int[3];
 
        // L R U D 순으로 1, 2, 3, 4 으로 표현
        // tail, head 초기화
        tail[0] = 1; // x좌표
        tail[1] = 1; // y 좌표
        tail[2] = 2; // 방향
        head[0] = 1;
        head[1] = 1;
        head[2] = 2;
 
        // 방향을 저장할 배열
        int[] moveY = { 0, -1, 1, 0, 0 };
        int[] moveX = { 0, 0, 0, -1, 1 };
 
        int time = 0;
        int headIdx = 0;
        // 움직이기 시작
        while (true) {
            time++;
            
            int nextX = head[0] + moveX[head[2]];
            int nextY = head[1] + moveY[head[2]];
 
            // 벽에 부딪힘 종료
            if (nextX == 0 || nextX == n + 1 || nextY == 0 || nextY == n + 1) {
                answer = time;
                break;
            }
            // 자기 자신과 맞닿으면 종료
            if (maps[nextX][nextY] > 0 && maps[nextX][nextY] != 5) {
                answer = time;
                break;
            }
 
            // 사과가 없는 경우 꼬리는 없애준다.
            if (maps[nextX][nextY] != 5) {
                maps[tail[0]][tail[1]] = 0; // 꼬리 없애주기
 
                // 이동방향으로 꼬리 이동하기
                tail[1] += moveY[tail[2]];
                tail[0] += moveX[tail[2]];
 
            }
            
            
            // 뱀의 머리 이동해주기
            head[0] = nextX;
            head[1] = nextY;
            maps[nextX][nextY] = head[2];
 
            
            if (changeDirTime[headIdx] == time) { // Head의 방향을 변경할
                head[2] = changeDirection(changeDir[headIdx], head[2]);
                maps[nextX][nextY] = head[2]; // 방향 바꿔줌
                headIdx++;
            }
            //맵에 표시된 tail의 이동 방향 확인
            tail[2] = maps[tail[0]][tail[1]]; // 맵에 표시된 방향으로 꼬리 방향 바꿔주기
 
            
        }
 
        System.out.println(answer);
 
    }
 
    static int changeDirection(String dir, int curDir) {
        if (dir.equals("L")) {
            if (curDir == 1)
                return 4;
            else if (curDir == 2)
                return 3;
            else if (curDir == 3)
                return 1;
            else
                return 2;
        } else {
            if (curDir == 1)
                return 3;
            else if (curDir == 2)
                return 4;
            else if (curDir == 3)
                return 2;
            else
                return 1;
        }
    }
}
 

스택으로 하여 Head, Tail 로 푸는 경우

0->없음

1->사과

2-> 뱀

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
class Solution {
    static int[][] maps;
    static int[] snakeX, snakeY;
    static int head,tail,n;
 
    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(new FileInputStream("C:\\Users\\SeonMi\\Desktop\\JavaTools\\Tools\\workspace\\SamsungGoGo\\sample_input.txt"));
        n = sc.nextInt();
        maps = new int[n+1][n+1];
        snakeX = new int[n*n];
        snakeY = new int[n*n];
        int k = sc.nextInt();
        for(int i=0;i<k;i++){
            maps[sc.nextInt()][sc.nextInt()]=1;
        }
        int l = sc.nextInt();
        int t=0;
        head=0; tail=0;
        boolean fin = false;
        int dir = 0;
        maps[1][1]=2;
        snakeX[head]=1;
        snakeY[head]=1;
        snakeX[tail]=1;
        snakeY[tail]=1;
        int[] moveX = {0,1,0,-1};
        int[] moveY = {1,0,-1,0};
        
        for(int i=0;i<l;i++){
            int changeTime = sc.nextInt();
            String changeDir = sc.next();
            
            while(t!=changeTime && !fin){
                t++;
                int x = snakeX[head]+moveX[dir];
                int y = snakeY[head]+moveY[dir];
                fin = move(x,y);
            }
            if(fin)
            {
                break;
            }
            if(changeDir.equals("L"))
                dir = (dir+3)%4;
            else
                dir = (dir+1)%4;
            
        }
        // 방향 변경이 끝나면 직진
        while(!fin){
            t++;
            int x = snakeX[head]+moveX[dir];
            int y = snakeY[head]+moveY[dir];
            fin = move(x,y);
        }
        System.out.println(t);
    }
 
    static boolean move(int x, int y) {
 
        if(x==0 || x==n+1 || y==0 || y==n+1)
            return true;
        
        if(maps[x][y]==2)
        {
            return true;
        }
        else if(maps[x][y]==0){ // 사과가 없는 경우 꼬리 제거
            maps[snakeX[tail]][snakeY[tail]]=0;
            tail++;
        }
        // 헤드 증가
        head++;
        snakeX[head]=x;
        snakeY[head]=y;
        maps[snakeX[head]][snakeY[head]]=2;
 
        
        return false;
    }
}