# [이.취.코] [백준] Chap 12. 구현 - Q11. 뱀

- Author: @mildsalmon
- Published: 2021-09-16
- Updated: 2021-09-17
- Source: http://blex.me/@mildsalmon/%EC%9D%B4%EC%B7%A8%EC%BD%94-%EB%B0%B1%EC%A4%80-chap-12-%EA%B5%AC%ED%98%84-q11-%EB%B1%80
- Tags: 파이썬, 알고리즘, 한빛미디어, 나동빈, 코딩테스트, 문제, 풀이, 구현, 백준, 삼성, 뱀

---

# 1. 뱀

- 난이도
	- 중 / 골5
- 풀이 시간
	- 40분
- 시간 제한
	- 1초
- 메모리 제한
	- 128 MB
- 출처
	- [3190번: 뱀 (acmicpc.net)](https://www.acmicpc.net/problem/3190)

### A. 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

### B. 내 답안

##### a. 1차 시도 (성공 / 시간초과)

```python

# 백준 3190번 문제  
  
from collections import deque  
  
n = int(input())  
  
# 게임 맵  
game_map = [[0] * (n+1) for _ in range(n+1)]  
  
# 사과 관련  
apple_count = int(input())  
apple_pos = []  
for i in range(apple_count):  
    # apple_pos.append(list(map(int, input().split())))  
 	x, y = list(map(int, input().split()))  
    game_map[x][y] = 2  
  
# 뱀의 방향 회전 관련  
snake_d_count = int(input())  
# snake_d_info = deque()  
snake_d_info = []  
for i in range(snake_d_count):  
    temp = list(input().split())  
    # snake_d_info.append([int(temp[0]), temp[1]])  
 	snake_d_info.append([int(temp[0]), temp[1]])  
  
# 뱀의 현재 방향  
d = 0  
# 뱀의 현재 방향에 따라 앞으로 갈 방향을 지정 (x - ds[d][0] 이런 식으로)  
ds = [(0,1), (1,0), (0,-1), (-1,0)]  
  
# 현재 뱀의 위치  
pos = [1, 1]  
# 뱀의 길이  
snake_length = 1  
# 게임 진행 시간  
time = 0  
  
# 머리 위치 저장하는 큐 // 생각해보니 머리는 스택으로 해도 될 듯  
# 루프가 반복될 때마다 머리에 저장된 데이터가 추출됨.  
# 머리는 시간이 지날때마다 다음 위치가 큐에 추가됨.  
q_head_pos = deque()  
q_head_pos.append(pos)  
  
# 꼬리 위치를 저장하는 큐  
# 다음 위치에 사과가 없으면 pop.# 사과가 있으면 그냥 반복해서 꼬리 위치 보전  
q_tail_pos = deque()  
q_tail_pos.append(pos)  
  
# 게임 시작시 뱀위 위치는 (맨위, 맨좌) = (1, 1)라서 map을 채우고 시작함.  
game_map[pos[0]][pos[1]] = 1  
# 방향 전환에 필요한 d를 가리키는 pointsnake_d_info_point = 0  
  
while True:  
    x, y = q_head_pos.popleft()  
  
    # 방향전환에 필요한 시간이 되면 방향 전환  
 	if len(snake_d_info) > snake_d_info_point:  
        if time == snake_d_info[snake_d_info_point][0]:  
            if snake_d_info[snake_d_info_point][1] == "D":  
                d = (d + 1) % 4  
  
			else:  
 	               d = (d - 1) % 4  
 			# d_info_time, d_info_move = snake_d_info.popleft()  
 			snake_d_info_point += 1  
  
	# 시간을 1초 증가시키고 다음 좌표를 탐색함.  
 	time += 1  
  
 	dx = x + ds[d][0]  
    dy = y + ds[d][1]  
  
    # 다음 좌표가 벽이거나 뱀의 몸통이면 게임 끝  
 	if dx < 1 or dx > n or dy < 1 or dy > n:  
        break  
  
 	if game_map[dx][dy] == 1:  
        break  
  
 	# 다음 좌표가 사과면 꼬리 유지, 사과가 아니면 꼬리 제거하고 맵 원상복구  
 	if game_map[dx][dy] != 2:  
        tx, ty = q_tail_pos.popleft()  
        game_map[tx][ty] = 0  
  
 	# 여기까지 왔으면, 장애물들은 다 통과한거니 맵을 채움.  
 	game_map[dx][dy] = 1  
  
	 # 다음 위치를 머리와 꼬리에 집어넣음.  
 	q_head_pos.append([dx, dy])  
    q_tail_pos.append([dx, dy])  
  
print(time)  
  
# 1시간 45분 / Pass

```

##### b. 2차 시도 (성공 / 시간초과)

```python

from collections import deque  
  
n = int(input())  
k = int(input())  
  
# 맵은 0으로 표시  
game_map = [[0]*(n+1) for _ in range(n+1)]  
  
# 사과는 2로 표시  
for i in range(k):  
    x, y = list(map(int, input().split()))  
    game_map[x][y] = 2  
  
l = int(input())  
snake_distance = []  
  
# 이것도 큐로 만들면 더 효율적일꺼 같음.  
# 밑에 for문을 쓰지 않아도 되니까  
for i in range(l):  
    time, d = list(input().split())  
    time = int(time)  
    snake_distance.append((time, d))  
  
# 뱀의 머리는 스택 / 굳이 스택이 아니여도 됨. 입력 -> 삭제를 반복하니까.  
# 뱀의 꼬리는 큐  
snake_head = [1, 1]  
snake_tail = deque()  
  
snake_tail.append((1, 1))  
  
# 동남서북  
# 처음 바라보는 방향이 오른쪽  
# 오른쪽에서 오른쪽으로 방향을 바꾸면 남  
# 왼쪽으로 방향을 바꾸면 북  
distance = [(0, 1), (1, 0), (0, -1), (-1, 0)]  
snake_d = 0  
time = 0  
  
# 게임은 종료조건을 만나기 전까지 끝나지 않음  
while True:  
    x, y = snake_head  
  
    # 뱀의 방향은 게임 시작 시간으로부터 X초가 끝난 뒤에 회전한다.  
 # 현재 시간과 뱀이 방향 바꾸는 시간을 비교하여 조건이 맞으면 방향을 바꿈  
 for s in snake_distance:  
        s_time, s_d = s  
        if s_time == time:  
            if s_d == "D":  
                snake_d = (snake_d + 1) % 4  
 elif s_d == "L":  
                snake_d = (snake_d - 1) % 4  
  
 # 시간을 추가함.  
 # 현재 시간(Line 51 앞부분)이 0일때, dx 부분의 시간(Line 57 뒷부분)은 1임.  
 time += 1  
  
 # 다음 위치를 예상해본다.  
 dx = x + distance[snake_d][0]  
    dy = y + distance[snake_d][1]  
  
    # 뱀이 벽에 부딪쳤을때  
 if dx < 1 or dx > n or dy < 1 or dy > n:  
        break  
 # 뱀이 자기 몸과 부딪쳤을 때  
 if game_map[dx][dy] == 1:  
        break  
  
 # 다음 위치에 사과가 없을 때  
 if game_map[dx][dy] != 2:  
        # 꼬리를 삭제하고 맵에서도 뱀의 꼬리 부분을 지운다.  
 tx, ty = snake_tail.popleft()  
        game_map[tx][ty] = 0  
 # 다음 위치에 사과가 있을 때  
 elif game_map[dx][dy] == 2:  
        pass  
  
 # 사과가 있든 없든, 다음 위치는 1(뱀)로 채움  
 # 뱀의 머리(스택), 꼬리(큐)에도 다음 위치를 추가함.  
 game_map[dx][dy] = 1  
 snake_head = [dx, dy]  
    snake_tail.append((dx, dy))  
  
print(time)

# 43분 32초

```

##### c. 회고

> 내 풀이

- 그냥 지문의 조건대로 구현했다.

> 반성

- 시간이 조금 걸렸다.
- 시간에 대한 문제 때문인데, (1,1)에서 뱀이 시작할 때를 1초로 잡고 구현했었다.
	- 문제는 `매 초마다 이동`, `게임 시작 시간으로부터 X초가 끝난 뒤`라고 제시되어 있다.
	- 그래서 (1,1)의 시작 시간은 0초, 종료 시간은 1초가 된다. 그리고 1초가 지났으니 이동하게 된다. (이 부분은 아래 그림으로 설명하겠다.)

> 결론

- 순서대로 차근차근 구현하면 되는데, 너무 뒤죽박죽으로 생각했다.
- 앞으로 이런 좌표 구현 문제는, 현재 위치와 다음 위치를 고려해서 구현해야겠다.
	- 다음 위치는 게임 종료 조건(제한 조건)을 검사하고 queue에 넣어주는 방식으로.

### C. 문제 해설

> 이해한 내용을 바탕으로 작성했습니다.

아래 그림을 보면 어떤 방식으로 구현해야하는지 감이 올 것이라 생각한다.

초보자는 손으로 그려보면서 해보는걸 추천한다.

![](https://static.blex.me/images/content/2021/9/16/9_DZpBsszuIEgq2x0QIW0K.jpg)

![](https://static.blex.me/images/content/2021/9/16/9_Gos2Syp6d5PJpdMy0Agh.jpg)

![](https://static.blex.me/images/content/2021/9/16/9_nQzQNf3KblWUW2kKMYbS.jpg)

![](https://static.blex.me/images/content/2021/9/16/9_ko6qVrMWDQlD6NE5fGAQ.jpg)

![](https://static.blex.me/images/content/2021/9/16/9_KDF4jyoAEIBSAIbqwmNw.jpg)

![](https://static.blex.me/images/content/2021/9/16/9_kHVAt6OdbQ1PhzNsrGxK.jpg)

##### a. 책 답안

[python-for-coding-test/5.py at master · ndb796/python-for-coding-test (github.com)](https://github.com/ndb796/python-for-coding-test/blob/master/12/5.py)

# 참고문헌

[1] 나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

[2] [3190번: 뱀 (acmicpc.net)](https://www.acmicpc.net/problem/3190). Baekjoon. (accessed Sep 15, 2021)