[백준] 3190번 뱀 (python)

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

---

 

접근 방식

초반에 문제 이해를 완전 잘못해서 오래 헤맸다..

 

헤맨 부분은 아래와 같다.

예를 들어

8 D
10 D

순으로 방향을 이동하는데, 이게 <8초 후 방향 전환 + 10초 후 방향 전환>이 아니라, <8초 후 방향 전환 + 그리고 2초 후 방향 전환>이다.

즉, 여기서 말하는 10초는 새로운 10초가 아니라 누적된 10초인 것이다..

 

그리고, 또 헤맨 부분은

예제 2번에서

8 D
10 D
11 D
13 L

이렇게 이동한다고 한다. 그런데 이때 13초가 지난 후 왼쪽으로 방향을 틀어준 다음 반복문을 끝내버렸다. 마지막으로 방향을 틀어줘도 앞으로 전진할 수 있음에도 불구하고 반복문을 끝내버렸다.

그래서 이 부분은 벽에 부딪히거나 자신의 몸에 닿은 경우가 아니면 float('inf')만큼 앞으로 가게 했다. 그러면 언젠가 벽에 부딪히기 때문이다. 만약, 벽에 부딪히거나 몸에 닿은 경우에는 바로 answer을 출력했다. 이건 앞으로 가지 못한다는 의미이기 때문이다.

 

문제 자체는 어렵지 않지만, 잘못 이해하면 엄청엄청엄청엄청 헤매게 되는 문제인 거 같다 (나만)

문제를 해결하는데 있어 가장 도움된 답변이다! 참고하면 좋을 거 같다. (https://www.acmicpc.net/board/view/103679)

 

 

정답 코드

import sys
from collections import deque
input = sys.stdin.readline

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
answer = 0
current = 0
snakes = deque([(0, 0)])

def change_direction(direction, current):
    if direction == "D": 
        return (current + 1) % 4 # 오른쪽
    else:
        return (current - 1) % 4 # 왼쪽
    

def move(time):
    global answer, snakes, current

    while answer < time:
        answer += 1

        nx, ny = snakes[0]
        nx += dx[current]
        ny += dy[current]

        if 0 <= nx < n and 0 <= ny < n:
            if [nx, ny] in snakes:
                return False
            
            snakes.appendleft([nx, ny])
            if board[ny][nx] != -1:
                snakes.pop()

            else:
                board[ny][nx] = 0
            
        else:
            return False

    return True
            

n = int(input())
k = int(input())
board = [[0] * n for _ in range(n)]

for _ in range(k):
    a, b = map(int, input().split())
    board[a-1][b-1] = -1


l = int(input())
time_direction = []

for _ in range(l):
    time_direction.append(list(map(str, input().split())))

flag = True
for time, direction in time_direction:
    if not move(int(time)):
        flag = False
        break

    current = change_direction(direction, current)

if flag:
    move(float('inf'))
    print(answer)
else:
    print(answer)