티스토리 뷰

PS/Problem_Solving

[BOJ] 3109.뱀(Queue,시뮬레이션)

Aaron 2020. 10. 30. 21:47
반응형


#. Problem

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

* The copyright in this matter is in BOJ




#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it


#. Solve

  

시뮬레이션 문제는 주어진 조건을 먼저 정리해놓는게 좋다.


종료 조건

뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.


뱀의 이동 조건

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

만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.

만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.


회전 조건

게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시


//


보면 뱀의 동작(머리는 길어지고, 꼬리는 짧아지는)은 Queue 자료구조와 융사하다는 것을 먼저 발견해야 한다.

오른쪽으로는 늘어나고(add), 왼쪽으로는 짧아지는(poll) Queue를 사용하면 쉽게 해결할 수 있다.


+


시뮬레이션은 분명히 '문제의 조건'을 잘 확인해야 하는데,

X초가 시작할 때 방향을 먼저 바꿔주다가 결국 문제를 다시 읽고 발견했다는...


#. Code


뱀의 방향 전환 정보는 Map<Integer, String>에 저장한 후,

.containKey("Key")로 확인하고 .get("Key")으로 방향 정보를 얻어서

적절한 때에 방향을 변환해주었다.


머리가 자기자신의 몸과 부딪히는지 확인하기 위해

equals()를 override 해주고 .contatins()로 확인해주었다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ3190 {
 
    static int N, K, L, map[][];
    static int[] dx = { 0, 1, 0, -1 }, dy = { 1, 0, -1, 0 }; // 동,남,서,북
    static Map<Integer, Character> oper;
    static Body head;
 
    static class Body {
        int x, y, dir;
 
        public Body(int x, int y, int dir) {
            super();
            this.x = x;
            this.y = y;
            this.dir = dir;
        }
 
        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            Body other = (Body) obj;
            if (x != other.x)
                return false;
            if (y != other.y)
                return false;
            return true;
        }        
    }
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine()); // 보드의 크기
        map = new int[N][N];
        K = Integer.parseInt(br.readLine()); // 사과의 개수
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
 
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            map[a][b] = 1;
        }
        L = Integer.parseInt(br.readLine()); // 뱀의 방향 변환 횟수
        oper = new HashMap<>();
        for (int i = 0; i < L; i++) {
            st = new StringTokenizer(br.readLine());
 
            oper.put(Integer.parseInt(st.nextToken()), st.nextToken().charAt(0));
        }
 
        System.out.println(process());
    }
 
    private static int process() {
 
        int time = 0;
        Queue<Body> body = new LinkedList<>();
        // 시작 위치는 (0,0)
        body.add(new Body(0, 0, 0));
        head = new Body(0, 0, 0);
 
        while (true) {
 
            time++;
            Body nextHead = new Body(head.x, head.y, head.dir);
 
            nextHead.x += dx[nextHead.dir];
            nextHead.y += dy[nextHead.dir];
 
            // 머리가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다
            if (body.contains(nextHead) 
                    || nextHead.x < 0 || nextHead.x >= N || nextHead.y < 0 || nextHead.y >= N)
                return time;
 
            // 이동한 칸에 사과가 있다면, 그 칸에 있던 사과는 없어지고 뱀 머리로
            if (map[nextHead.x][nextHead.y] == 1) {
                map[nextHead.x][nextHead.y] = 0;
            }
            // 이동한 칸에 사과가 없다면, 몸 길이를 줄여서 꼬리가 위치한 칸을 비워준다.
            else {
                body.poll();
            }
 
            // 방향 전환
            if (oper.containsKey(time)) {
                char d = oper.get(time);
                // 왼쪽(C가 'L') 또는 오른쪽(C가 'D')
                if (d == 'D') {
                    nextHead.dir = (nextHead.dir + 1) % 4;
                } else {
                    nextHead.dir = (nextHead.dir + 3) % 4;
                }
            }
            
            // 머리를 몸에 추가
            body.add(nextHead);
            // 머리 정보 갱신
            head = new Body(nextHead.x, nextHead.y, nextHead.dir);
        }
    }
}
cs





반응형
저작자표시

'PS > Problem_Solving' 카테고리의 다른 글

[SWEA] 1952.수영장(dfs, dp).java  (0) 2020.11.01
[BOJ] 5002. 도어맨(Greedy, 문자열).java  (0) 2020.11.01
[BOJ] 12208.Super 2048 (Small)(시뮬레이션).java  (0) 2020.10.30
[SWEA] 1824. 혁진이의 프로그램 검증.java  (0) 2020.10.30
[BOJ] 14890.경사로(구현).java  (0) 2020.10.28
댓글
최근에 올라온 글
최근에 달린 댓글
링크
Total
Today
Yesterday
TAG more