사용자 도구

사이트 도구


ps:problems:boj:3190

ps
링크acmicpc.net/…
출처BOJ
문제 번호3190
문제명
레벨골드 5
분류

구현

시간복잡도O(n)
인풋사이즈n<=10000
사용한 언어Python
제출기록32508KB / 100ms
최고기록60ms
해결날짜2022/04/26
태그

[라이] 리스트/배열/연결 리스트

풀이

  • 시키는대로 구현해주면 되는 문제.
  • 뱀이 차지하고 있는 좌표들를 덱에 저장해서, 뱀이 머리의 위치가 덱의 맨 앞에, 꼬리의 위치가 덱의 맨 뒤에 저장되도록 하면, 뱀의 이동을 덱의 맨 뒤의 원소를 제거하고 맨앞에 이동하는 새 좌표를 추가하는 식으로 O(1)에 처리할수 있다.
  • 마찬가지로 2차원 배열에도 뱀의 차지하고 있는 좌표들을 저장한다면, 새로 이동한 곳에 뱀에 몸통이 있어서 충돌하는지 여부를 O(1)에 체크할수 있다.
  • X초동안 시뮬레이션 하고, 매초마다 O(1)의 계산이 필요하므로 총 시간복잡도는 O(X)

코드

"""Solution code for "BOJ 3190. 뱀".

- Problem link: https://www.acmicpc.net/problem/3190
- Solution link: http://www.teferi.net/ps/problems/boj/3190

Tags: [Implementation]
"""

import collections

APPLE = 'A'
SNAKE = 'S'
EMPTY = 'E'
DELTAS = [(0, 1), (1, 0), (0, -1), (-1, 0)]
INF = float('inf')


def main():
    N = int(input())
    grid = [[EMPTY] * N for _ in range(N)]
    K = int(input())
    for _ in range(K):
        apple_r, apple_c = [int(x) for x in input().split()]
        grid[apple_r - 1][apple_c - 1] = APPLE
    L = int(input())
    turns = []
    for _ in range(L):
        X, C = input().split()
        turns.append((int(X), C))

    turns.append([INF, 'X'])
    r, c = 0, 0
    grid[r][c] = SNAKE
    queue = collections.deque([(r, c)])
    direction = 0
    dr, dc = DELTAS[direction]
    t = 0
    for X, C in turns:
        while t < X:
            t += 1
            r, c = r + dr, c + dc
            if not (0 <= r < N and 0 <= c < N) or grid[r][c] == SNAKE:
                break
            if grid[r][c] == EMPTY:
                tail_r, tail_c = queue.popleft()
                grid[tail_r][tail_c] = EMPTY
            grid[r][c] = SNAKE
            queue.append((r, c))
        else:
            direction = (direction + (1 if C == 'D' else -1)) % 4
            dr, dc = DELTAS[direction]
            continue
        break

    print(t)

토론

댓글을 입력하세요:
Q S A D L
 
ps/problems/boj/3190.txt · 마지막으로 수정됨: 2022/05/03 09:36 저자 teferi