sw Yoo

sw Yoo

No sweat, no sweet

In [1]: 
1
2
3
4
5
6

import sys
sys.path.append("/home/swyoo/algorithm/")
from sys import stdin
from collections import deque
from utils.verbose import logging_time
import numpy as np

3190. 뱀

주어진 조건에 따라 구현하고, 결과 값을 return.

Parse Data

Given a $N\times N$ grid, $K$ apples, $L$ moves, count seconds at the terminal state.

  1. 주어진 apple의 위치, moves에서 시간 등을 $O(1)$에 바로 검색할 수 있도록, set으로 바꾸어 저장.
  2. rotate 할 수 있도록 inline 함수를 따로 lambda function을 이용해서 구현 해 놓았다.

    앞으로도 많이 사용될 수 있는 tip이 될 것 같다.

주의사항 

        1. apples 의 인덱스를 구할때, 주어진 데이터는 번째 수를 의미하므로 -1을 뺀다.
        2. up, down, left, right 실수하지 않도록 주의

In [2]: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14

stdin = open('data/snail.txt')  # 제출 시 주석처리
input = stdin.readline
plot = lambda a: print(np.array(a))
N, K = int(input()), int(input())
grid = [[0] * N for _ in range(N)]
apples = set(tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(K))
L = int(input())
moves = []
for _ in range(L):
    move = input().split()
    moves.append((int(move[0]), move[1]))
moves = {k: v for k, v in moves}
up, down, left, right = (-1, 0), (1, 0), (0, -1), (0, 1)
rotate = lambda i, j, kind: (j, -i) if kind == 'D' else (-j, i)

Implementation

주어진 grid 안에서 계속 이동하다가, 나가는 조건이 생기면, 그때 break한다.

  • deque를 사용하여, head 값과 tail값을 $O(1)$에 추적가능 하도록 하였다.
  • 적절한 위치에 조건문들을 구현.
    • 일단 자기 꼬리에 부딛히면 break.
    • 사과를 먹고, 꼬리가 늘어날 조건 .
    • move명령이 있다면 다음 스텝(step) 부터는 dx, dy 가 변경되도록 업데이트.

끝나게 된 시점의 시간이 추가되어야하므로 return ans + 1

In [3]: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

@logging_time
def solution(grid, apples, moves, show=False):
    ans = x = y = 0
    dx, dy = right
    Q, grid[x][y] = deque([(x, y)]), '#'  # left most means the tail.
    plot(grid)
    x, y = x + dx, y + dy  # (x, y) means the head.
    while 0 <= x < N and 0 <= y < N:
        if grid[x][y]: break
        _, grid[x][y] = Q.append((x, y)), '#'
        if (x, y) in apples:
            apples.discard((x, y))
        else:
            tail = Q.popleft()
            grid[tail[0]][tail[1]] = 0

        ans += 1
        if show: plot(grid), print(ans)
        if ans in moves:
            dx, dy = rotate(dx, dy, moves[ans])
        x, y = x + dx, y + dy
    return ans + 1

print(solution(grid, apples, moves, show=True, verbose=True))

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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

[['#' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']]
[['#' '#' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']]
1
[['#' '#' '#' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']]
2
[['0' '#' '#' '#' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']]
3
[['0' '#' '#' '#' '#' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']]
4
[['0' '#' '#' '#' '#' '#' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']]
5
[['0' '#' '#' '#' '#' '#' '#' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']]
6
[['0' '0' '#' '#' '#' '#' '#' '#' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']]
7
[['0' '0' '0' '#' '#' '#' '#' '#' '#' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']]
8
[['0' '0' '0' '0' '#' '#' '#' '#' '#' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '#' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']]
9
[['0' '0' '0' '0' '0' '#' '#' '#' '#' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '#' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '#' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']]
10
[['0' '0' '0' '0' '0' '0' '#' '#' '#' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '#' '0']
 ['0' '0' '0' '0' '0' '0' '0' '#' '#' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']]
11
[['0' '0' '0' '0' '0' '0' '0' '#' '#' '0']
 ['0' '0' '0' '0' '0' '0' '0' '#' '#' '0']
 ['0' '0' '0' '0' '0' '0' '0' '#' '#' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']
 ['0' '0' '0' '0' '0' '0' '0' '0' '0' '0']]
12
WorkingTime[solution]: 4.46701 ms
13

Submitted Code

In [4]: 
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

import sys
from sys import stdin
from collections import deque
# import numpy as np

stdin = open('data/snail.txt')  # 제출 시 주석처리
input = stdin.readline
# plot = lambda a: print(np.array(a))
N, K = int(input()), int(input())
grid = [[0] * N for _ in range(N)]
apples = set(tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(K))
L = int(input())
moves = []
for _ in range(L):
    move = input().split()
    moves.append((int(move[0]), move[1]))
moves = {k: v for k, v in moves}
up, down, left, right = (-1, 0), (1, 0), (0, -1), (0, 1)
rotate = lambda i, j, kind: (j, -i) if kind == 'D' else (-j, i)

def solution(grid, apples, moves):
    # plot(grid)
    ans = x = y = 0
    dx, dy = right
    Q, grid[x][y] = deque([(x, y)]), '#'  # left most means the tail.
    x, y = x + dx, y + dy  # (x, y) means the head.
    while 0 <= x < N and 0 <= y < N:
        if grid[x][y]: break
        _, grid[x][y] = Q.append((x, y)), '#'
        if (x, y) in apples:
            apples.discard((x, y))
        else:
            tail = Q.popleft()
            grid[tail[0]][tail[1]] = 0

        ans += 1
        # plot(grid), print(ans)
        if ans in moves:
            dx, dy = rotate(dx, dy, moves[ans])
        x, y = x + dx, y + dy
    return ans + 1

print(solution(grid, apples, moves))

1
2

13

Report

simulation하는 문제는 구현 능력을 테스트 하기 위함이다.
꼼꼼히 조건을 체크하는 것이 중요하다.
queue를 사용하는 것에 대해 연습해 볼 수 있는 문제였다.

Reference

[1] beakjoon 뱀

Leave a comment

You may also enjoy

Reeds-Shepp (RS) Path

18 minute read

이동체의 운동 구속조건을 반영하면 전진과 후진 경로에 대한 48가지 경로의 조합을 체크하는 RS path를 배워보자.

Model Predictive Control (MPC)

17 minute read

motion model로 다음 상태를 예측하여 비용함수를 만들고 모델을 제약사항으로 최적화를 하여 제어값을 찾아내는 MPC에 대해서 배워보자

RRT star

15 minute read

RRT star 알고리즘에 대해서 알아보자.