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

  • 0
  • 0
0
0

1. 뱀

A. 문제

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

B. 내 답안

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

# 백준 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차 시도 (성공 / 시간초과)

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. 문제 해설

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

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

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

a. 책 답안

python-for-coding-test/5.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

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

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

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.