BOJ3190_뱀

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

문제요약

1. 사과를 먹으면 뱀 길이가 늘어난다

2. 벽 또는 자신의 몸에 부딪히면 게임이 끝난다

3. 게임이 시작할 때 뱀은 맨위 맨좌측(1,1)에 위치하고 뱀의 길이는 1 이다 , 처음에는 오른쪽으로 향한다

4. 매초 마다 이동하는 규칙

(1) 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다

(2) 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다(몸 길이가 늘어난다)

(3) 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워 준다

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

6. 사과 : 사과의 위치는 모두 다르다 , (1,1)에는 사과가 없다

7. 뱀 이동 : X C , 게임 시작 시간으로부터 X초가 끝난 뒤에 C방향으로 90도 회전 , X는 10,000이하의 양의 정수 , C는 D오른쪽 L왼쪽

문제issue

1. 자신의 몸에 부딪히는 경우

-> map[r][c]가 1이면 break

2. 벽에 부딪히는 경우는 그냥 인덱스 넘어가면 종료

3. 처음에 뱀의 몸 길이가 늘어나는 부분과 뱀이 움직이는 부분이 헷갈려서

0 0 1 1 1 0            0 0 0 1 1 0 

0 0 0 0 2 0     ->    0 0 0 0 1 0

0 0 0 0 0 0            0 0 0 0 2 0

2가 뱀의 머리라고 했을 때 위와 같이 움직이면 꼬리부분을 0으로 만들고

머리와 몸통부분은 움직인다고 생각하고 어떤 몸통은 행을 증감시키고 어떤 몸통은 열을 증감시켜야 할지 헷갈렸음

계속 그리다 보니 그냥 머리만 추가 해주고 경우에 따라서 꼬리를 지울지 말지만 정해주면 됨

전 단계에서 머리였던 부분이 몸통으로 변함 즉, 몸통에 해당하는 배열의 인덱스를 따로 변화시킬 필요가 없었음

4. 뱀의 꼬리가 어디인지

-> 큐를 사용

해결흐름

1. 사과의 위치는 2 , 뱀은 1 , 빈칸 0 인 map을 만든다

2. 몇 초가 지났을 때 L 또는 D를 수행하기 위해서 char 배열을 만들어서

order_arr[몇초] = L 또는 D 이런식으로 세팅한다

3. 처음 뱀의 머리에 해당하는 부분을 큐에 add해준다

4. 방향 dir에 따라서 행 또는 열을 변화 시켜준다

5. 변화된 행 또는 열이 범위안인지 검사하고 범위밖이면 flag = ture 후 return한다

flag = true면 while문도 종료 시킨다

6. 범위안이면 빈 칸인지 0 , 사과인지 2 , 뱀의 일부인지 1로 나눈다

7. 빈 칸이면 q.poll해서 꼬리에 해당하는 칸을 꺼내주고 map에서 0으로 갱신해준뒤 , 새로운 머리 위치를 q.add해주고 map에도 갱신해준다

8. 사과면 visited 체크만 해준뒤 , map 갱신 , q.add만 해준다

9. 뱀의 몸이면 flag = true 해준뒤 return 해준다

10. order_arr[result]에 L 또는 D가 있으면 그때의 dir에 따라서 dir을 갱신해준다

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    static class pair {
        int r;
        int c;
 
        public pair(int r, int c) {
            super();
            this.r = r;
            this.c = c;
        }
    }
    
    private static int[] dr = {0,0,-1,1};
    private static int[] dc = {1,-1,0,0};
 
    private static int N;
    private static int dir;
    private static int s_r;
    private static int s_c;
    private static int result;
    private static boolean flag;
    private static LinkedList<pair> q;
    private static char[] order_arr;
    private static int[][] map;
    private static boolean[][] apple_visited;
 
    public static void main(String[] args) throws Exception {
 
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine().trim());
        map = new int[N + 1][N + 1];
        apple_visited = new boolean[N + 1][N + 1];
        int K = Integer.parseInt(br.readLine().trim());
        for (int i = 0; i < K; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
            // 사과위치
            map[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = 2;
        }
        // 뱀의 처음 위치
        map[1][1] = 1;
        int L = Integer.parseInt(br.readLine().trim());
        // 몇초가 지났을 때 회전하는 정보를 저장 , 몇초가 인덱스에 해당하고 거기에 L또는D를 저장
        order_arr = new char[10000];
        for (int i = 0; i < L; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
            order_arr[Integer.parseInt(st.nextToken())] = st.nextToken().charAt(0);
        }
 
        // start
        result = 0;
        dir = 0; // 0오른쪽 , 1왼쪽 , 2위 , 3아래 처음에는 오른쪽
        s_r = 1; // 뱀 처음 위치
        s_c = 1;
        q = new LinkedList<pair>();
        q.add(new pair(s_r, s_c));
        flag = false;
        while (true) {
            result++;
            // 방향에 따라서
            s_r += dr[dir];
            s_c += dc[dir];
            solve();
            if(flag)
                break;
        }
        System.out.println(result);
    } // end of main
 
    private static void solve() {
        // 범위 안이고
        if (s_c >= 1 && s_c <= N && s_r >= 1 && s_r <= N) {
            // 빈곳이면 머리 위치를 add해주고 , 꼬리는 poll해서 map을 갱신
            if (map[s_r][s_c] == 0) {
                pair p = q.poll();
                map[p.r][p.c] = 0;
                q.add(new pair(s_r, s_c));
                map[s_r][s_c] = 1;
            } else if (map[s_r][s_c] == 2 && !apple_visited[s_r][s_c]) {
                // 사과면
                apple_visited[s_r][s_c] = true;
                map[s_r][s_c] = 1;
                q.add(new pair(s_r, s_c));
            }
            // 뱀의 몸이면
            else if (map[s_r][s_c] == 1) {
                flag = true;
                return;
            }
        } else {
            // 범위를 넘어가면
            flag = true;
            return;
        }
        // 방향 검사하고 변경
        if (order_arr[result] == 'L') {
            if(dir==0)
                dir = 2;
            else if(dir == 1)
                dir = 3;
            else if(dir == 2)
                dir = 1;
            else if(dir == 3)
                dir = 0;
        } else if (order_arr[result] == 'D') {
            if(dir == 0)
                dir = 3;
            else if(dir == 1)
                dir = 2;
            else if(dir == 2)
                dir = 0;
            else if(dir == 3)
                dir = 1;
        }
    }
} // end of class