3190 뱀 (Python)

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

import sys
input = sys.stdin.readline

N=int(input())

# 사과 받기
K=int(input())
apple=[[False for _ in range(N)] for _ in range(N)]
for _ in range(K):
    a, b = map(int,input().split())
    apple[a-1][b-1] = True

# 방향 변환 정보 받기
L = int(input())
dir = []
for _ in range(L):
    dir.append(list(input().split()))
dir.append([0,0])

# 오른쪽으로 방향 90도 회전
# (0,1) -> (1,0)
# (1,0) -> (0,-1)
# (0,-1) -> (-1,0)
# (-1,0) -> (0,1)

# 방향 변환 정보는 0이 될 때까지 계속 확인,
# 시간이 일치하면 방향을 바꾸고 다음 인덱스로 넘어감
def changeDirection(direction, time):
    global idxD
    if int(direction[0]) == time:
        # 오른쪽으로 방향 회전
        if direction[1] == 'D':
            idxD += 1
            return 1
        else:
            idxD += 1
            return -1
    else:
        return 0

from collections import deque
# 꼬리는 가장 처음 들어간 값

# heading만큼 좌표를 더해준 후에
# 게임이 끝났는지 확인하고
# 사과를 못 먹었다면 꼬리를 삭제한다
# 시간을 더해준다
# 방향을 바꿔준다

# 방향을 관리하는 정보들
heading = [[0,1],[1,0],[0,-1],[-1,0]]
idxH = 0
idxD = 0
# 꼬리부터 큐로 들어간다
body = deque()
bodyArr = [[False for _ in range(N)] for _ in range(N)]
body.append([0,0])
time = 0

while(1):
    head = [body[-1][0] + heading[idxH%4][0], body[-1][1] + heading[idxH%4][1]]
    body.append(head)
    # 시간을 더해준다
    time += 1
    # 벽에 부딪히면 종료
    if not ((0 <= head[0] < N) and (0 <= head[1] < N)):
        break
    # 자기 몸에 부딪히면 종료
    if bodyArr[head[0]][head[1]] == True:
        break
    bodyArr.append(head)
    bodyArr[head[0]][head[1]] = True
    # 사과가 없으면 꼬리 삭제
    if not apple[head[0]][head[1]]:
        bodyArr[body[0][0]][body[0][1]] = False
        body.popleft()
    else:
        apple[head[0]][head[1]] = False
    # 방향을 바꿔준다
    idxH += changeDirection([dir[idxD][0],dir[idxD][1]],time)

print(time)

나의 풀이

 

문제에서 주어지는 조건이 널널해서 최적화 안 하고 풀어도 되는 부분이 많았다.

 

예를 들면, 어차피 방향 전환의 개수가 별로 안 많아서
def changeDirection(direction, time): 이 함수 안 만들고

 

 if time in time_dic:
        # 만약 시계방향으로 돈다면
        if time_dic[time] == 'D':
            d = (d + 1) % 4
        else:
            d = (d - 1) % 4

코드 출처 : https://ji-gwang.tistory.com/473

 

이런 식으로 대충 해버려도 됐을텐데, 괜히 발상하고 함수 쓰는데에 시간 날렸다.

실전에서 문제 빨리 풀 때도 어디까지 최적화를 안해도 되는지를 잘 생각해야겠다.
그러니까, 풀이 작성 시간과 시간 복잡도 사이의 trade-off를 잘 조율해야겠다.

 

    # 벽에 부딪히거나 자기 몸과 부딪히면
    if x < 0 or x >= N or y < 0 or y >= N or arr[x][y] == 2:
        break
    # 벽이 아니면
    # 사과가 없다면
    if not arr[x][y]:
        # 꼬리 없애주고
        i, j = snake.popleft()
        arr[i][j] = 0

위와 같은 블로그의 코드인데,

1. arr를 따로 만들지 않고 한 곳에서 정보를 취합한 점, (0,1,2로 정보 구분)
2. 어차피 자기 자신의 몸이 있는지는 앞에서 확인했으니 뒤에서는 배제하고 if not arr[x][y]만 사용한 점

이것들이 코드가 깔끔한 요인.

사실 테크닉들은 알고 있었는데 빨리 풀어야겠다는 조급함이 있었다보니까
시야가 좁아져서 떠올리지도 못했다. 결국 실력 문제긴 함.
긴장하거나 조급해져도 바로바로 떠올릴 수 있어야 함.

 

# 우하좌상
dx = [0, 1, 0, -1]  # 행
dy = [1, 0, -1, 0]  # 열

...

x += dx[d]
y += dy[d]

이 부분도 아이디어가 좋다.

dx랑 dy를 따로 만들어놓고 같은 인덱스로 접근해버리면
[[0,1],[1,0],[0,-1],[-1,0]] 이랑 같은 효과를 냄.

 

내 풀이는 2차원 배열이라 코드 더러웠음.