[백준 3190] 뱀 (Python)

👩🏻‍💻문제설명

[백준 3190] 뱀 (Python)

문제요약

(0, 0) 지점에서 시작하고, 머리는 오른쪽을 바라보고 있다.
머리 : 항상 이동할 다음 칸을 바라보고 있다.

이동한 칸에 사과가 있는 경우 : 꼬리는 움직이지 않음
이동한 칸에 사과가 없는 경우 : 꼬리칸 비우기

종료 조건 : 자기 자신 또는 벽과 닿았을 때 종료한다.
게임이 몇 초 뒤에 끝나는가?

입력

첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)

다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.

다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)

다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데, 정수 X와 문자 C로 이루어져 있으며. 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.

출력

첫째 줄에 게임이 몇 초에 끝나는지 출력한다.

예제 입력 1
6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

예제 출력 1
9

예제 입력 2
10
4
1 2
1 3
1 4
1 5
4
8 D
10 D
11 D
13 L

예제 출력 2
21

예제 입력 3
10
5
1 5
1 3
1 2
1 6
1 7
4
8 D
10 D
11 D
13 L

예제 출력 3
13

✍️Idea Sketch

알고리즘 : 구현

문제에서 주어진 대로 로직을 작성하면 되는 구현 문제이다. 뱀의 머리칸과 꼬리칸을 계속 갱신해야 하므로 Queue로 구현하였다.

시간복잡도

O(n)

첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) … 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, …

위 글을 통해 최악의 경우 10,000초일 때 마지막으로 방향을 변환하고 계속 직진함을 알 수 있다. 보드의 크기 N는 최대 100이므로 100초 후에는 무조건 벽에 부딪힌다. 따라서 뱀의 최대 이동시간은 약 10,100초이다.

✍️내 소스코드

• 2차원 배열 graph에 사과 위치를 1로 표시한다.
• 뱀의 머리칸과 꼬리칸을 계속 갱신해야 하므로 Queue로 구현한다. 이 때 뱀의 좌표와 방향 정보 2개가 필요하므로 Queue를 2개 사용한다. snake, direction
• 뱀의 방향 변환 정보 turnHead도 Queue로 구현한다.
• 반복문에서 뱀의 최대 이동시간은 약 10,100초이나 여유롭게 20,000으로 설정했다. for time in range(1, 20000):
• 뱀의 머리가 이동한 칸 nx, ny를 선언하고, 자기자신 또는 벽과 부딪히는지 확인한다. (종료 조건)
• 계속 진행한다면, 뱀의 머리가 이동한 칸 nx, ny와 방향 정보를 snake, direction Queue에 추가한다.
• 방향을 변환할 타이밍인 경우, 변환한 방향 정보를 direction Queue에 추가해야 한다.
• 이동한 칸에 사과가 있는 경우 사과를 없애고, 그렇지 않은 경우 꼬리칸을 비운다.

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

  # 오른쪽, 아래쪽, 왼쪽, 위쪽 (시계방향) --> L이면 -1, D면 +1 index
  dx = [0, 1, 0, -1]
  dy = [1, 0, -1, 0]

  n = int(si())
  graph = [[0] * n for _ in range(n)]

  k = int(si())

  for _ in range(k):
    a, b = map(int, si().split())
    graph[a-1][b-1] = 1 # 사과

  snake = deque([(0, 0)])
  direction = deque([0])

  l = int(si())

  turnHead = deque()
  for _ in range(l):
    x, c = si().split()
    turnHead.append((int(x), c))

  for time in range(1, 20000):
    hx, hy = snake[0]
    nx, ny = hx + dx[direction[0]], hy + dy[direction[0]]

    if (nx, ny) in snake:
      break
    if not (0 <= nx < n) or not (0 <= ny < n):
      break

    snake.appendleft((nx, ny))

    if turnHead and time == turnHead[0][0]:
      x, c = turnHead.popleft()

      if c == 'L':
        direction.appendleft((direction[0] + 3) % 4)
      else:
        direction.appendleft((direction[0] + 1) % 4)
    else:
      direction.appendleft(direction[0])

    if graph[nx][ny] == 1:
      graph[nx][ny] = 0
    else:
      snake.pop()
      direction.pop()

  print(time)