[백준 3190] 뱀 python (tc5 tc6 틀림)

 

회사 인턴분의 추천으로 BFS 다음 연습 대상으로 구현을 선택했다.

 

유명한 구현 문제로 구현 문제 연습을 시작했다.

회사 다녀서 맨날 코드짜서 그런지 시간이 오래 걸려도 그냥 풀면 풀린다. 

 

from collections import deque

def snake(deque):
  direction = 0;
  deque.append([1,1])
  for sec in range(1,10100):
    new_location = [deque[len(deque)-1][0] + dy[direction], deque[len(deque)-1][1] +dx[direction] ]
    location = deque.popleft()
    if new_location[0] > N or new_location[1] > N or new_location[0] ==0 or new_location[1] ==0:
      return sec
    if new_location in deque or new_location ==location:
      return sec
    if new_location in apple:
      deque.appendleft(location)
      apple.remove(new_location)
    deque.append(new_location)
    
    if move[sec] =="D":
      direction +=1
      if direction ==4:
        direction =0
    
    if move[sec] =="L":
      direction -=1
      if direction ==-1:
        direction =3

### get input
N =int(input())
K = int(input())
apple  = []

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

for i in range(K):
  apple.append(list(map(int,input().split(" "))))

L = int(input())
move =[ "X" for _ in range(10100)]

for i in range(L):
  time, direction = input().split(" ")
  move[int(time)] = direction

deque = deque()
print(snake(deque))

내가 놓쳤던 부분은  

1.  0,0 에도 벽이 있다는 점과 

2. 사과를 한번 먹고나면 제거해 주어야 함

3. 자기 몸에 닿았을 때도 죽는다. 

 

이렇게 두가지였다. 

 

1번과 3번은 문제에 주어진  테스트케이스를 돌리다 찾아냈고, 2번은 틀리고나서 테스트케이스를 찾다가 발견했다.

 

 

백준에서 공개된 테스트케이스를 이용해봤다. 

#tc5

35
28
21 2
22 23
3 5
34 30
29 31
3 28
20 12
27 26
31 7
5 10
21 10
19 2
15 23
4 23
3 19
3 35
13 30
30 30
23 27
32 17
22 24
8 27
4 8
30 18
15 28
22 29
28 5
16 33
20
27 D
61 L
68 L
100 L
133 L
160 L
165 D
168 D
170 D
182 D
206 D
207 D
214 D
215 D
216 L
237 D
240 D
241 L
251 D
252 D

output: 237

#########

#tc6:

58
58
31 50
13 34
54 27
21 40
17 36
28 48
38 27
13 51
53 44
28 57
10 25
26 20
29 31
2 6
53 24
19 45
31 58
30 36
2 33
52 31
22 30
15 56
44 36
26 12
47 18
10 57
4 5
28 52
6 30
48 15
5 38
25 38
29 48
50 40
36 5
35 15
45 9
56 42
18 15
51 9
33 29
26 47
46 28
43 29
16 41
16 30
38 35
49 14
20 7
39 50
21 36
40 25
9 5
6 4
49 23
15 32
41 4
42 2
78
5 D
8 D
10 L
15 L
17 L
18 L
20 L
32 L
64 D
65 L
76 D
81 L
82 D
86 L
87 D
88 L
91 L
94 D
100 D
103 D
107 D
109 L
110 D
111 D
115 D
116 L
117 D
118 D
119 L
120 L
121 D
143 D
192 D
229 D
276 L
287 L
313 L
365 D
366 D
403 L
404 L
439 D
440 D
463 L
464 L
469 D
470 L
482 D
493 D
494 D
498 L
510 L
513 D
514 L
519 L
520 D
529 L
545 L
552 D
558 D
564 D
565 D
568 L
570 L
574 D
576 D
581 D
588 D
597 D
619 D
672 D
678 D
693 D
742 L
743 L
747 D
748 L
751 L

output:586

 

 

 

이렇게 두가지 테스트케이스에서 에러가 났는데

이 경우는 사과를 먹고 나서 치워주지 않은 경우에 발생하게 된다.