[백준] 3190번 뱀 파이썬

NxN 정사각 보드 위에 몇 칸에는 사과가 있음.

보드의 상하좌우 끝에는 벽 설치.

뱀의 길이 : 1 / 뱀 처음 위치 : 맨위 좌측 / 처음 오른쪽 이동

뱀은 사과를 먹으면 길이가 늘어나고 벽 또는 자기자신과 몸을 부딪히면 게임 종료..!

 

<뱀 이동 규칙>

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

 

- 입력

1줄 : 보드의 크기 N (2 ≤ N ≤ 100) 

2줄 : 사과의 개수 K (0 ≤ K ≤ 100)

K줄 : 사과의 위치(행, 열)   *1행 1열에는 사과가 없음.

다음줄 : 뱀의 방향 변환 횟수 L (1 ≤ L ≤ 100)

L줄 : 뱀의 방향 변환 정보(X와 C)   * 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전

 

- 출력

게임이 종료되는 시간 초

 

고민) 전체 보드에서 사과의 위치에 True를 넣고, 없는 곳은 False를 넣는다. 뱀이 1행 1열 즉 board[0][0]부터 존재하므로 해당 칸은 숫자 1을 넣는다. board를 탐색할 때에 true를 만나면 해당 칸 정보를 1로 변경한다. 

n = int(input())
k = int(input())
apple = [list(map(int, input().split())) for _ in range(k)]
l = int(input())
snack = [list(map(int, input().split())) for _ in range(l)]

snack = [[0,0]]
head = snack[0]
tail = snack[0]

board = [[0]*n for _ in range(n)]
def make_board():
  for a in apple:
    for i in range(n):
      for j in range(n):
        if a[0] == i and a[1] == j:
          board[i][j] = True
        else:
          board[i][j] = False

  board[0][0] = 1
  return board

#오, 아래, 왼, 위
direction = [[1,0], [0,-1], [-1,0], [0,1]]

def move_snack(board, direction):
  
  if board[head[0]+direction[0]][head[1]+direction[1]] == 1:
    return "terminate"
  if head[0]+direction[0] < 0 or head[0]+direction[0] >=n or head[1]+direction[1] < 0 or head[1]+direction[1] >= n:
    return "terminate"
    
  if board[head[0]+direction[0]][head[1]+direction[1]] == True:
    head[0], head[1] = head[0]+direction[0], head[1]+direction[1]
    board[head[0]+direction[0]][head[1]+direction[1]] = 1
    snack.instert(0, head)
    
  else:
    head[0], head[1] = head[0]+direction[0], head[1]+direction[1]
    board[head[0]+direction[0]][head[1]+direction[1]]
    snack.instert(0, head)
    tail = snack.pop()
    board[tail[0]][tail[1]] = False
    
  return new_board


make_board()
t = 0
while(True):
  t += 1
  d = 0
  direction = direction[d] #오른쪽방향
  new_board = board[:]

  for s in snack:
    if s[0] == t:
      if s[1] == 'L':
        temp = move_snack(new_board, direction) 
        if temp == "terminate":
          break
        else:
          new_board = temp
        direction = direction[d-1]
      else:
        temp = move_snack(new_board, direction)
        if temp == "terminate":
          break
        else:
          new_board = temp
        direction = direction[d+1]
    else:
      temp = move_snack(new_board, direction)
      if temp == "terminate":
          break
      else:
          new_board = temp

print(t)

우선 사과 위치를 board에 넣을 때에 인덱스임을 고려해서 좌표-1을 주의해야했음.

 

3190번 뱀

해답1) while문 구현

from collections import deque


n = int(input())
k = int(input())
graph = [[0] * n for _ in range(n)]
dx, dy = (0, 1, 0, -1),  (1, 0, -1, 0)
for _ in range(k):
    x, y = map(int, input().split())
    graph[x - 1][y - 1] = 2

l = int(input())
turns = dict()
for _ in range(l):
    s, d = input().split()
    turns[int(s)] = 1 if d == "D" else -1

sec = 0
x, y, d = 0, 0, 0
snake = deque([(0, 0)])
graph[0][0] = 1

while True:
    sec += 1
    x, y = x + dx[d], y + dy[d]

    if not 0 <= x < n or not 0 <= y < n or graph[x][y] == 1:
        break

    if graph[x][y] == 0:
        snake.append((x, y))
        graph[x][y] = 1
        a, b = snake.popleft()
        graph[a][b] = 0
    elif graph[x][y] == 2:
        snake.append((x, y))
        graph[x][y] = 1

    if sec in turns:
        d = (d + turns[sec]) % 4

print(sec)

 

해답2) for문 구현

# 보드의 크기 입력받기
n = int(input())

# 뱀이 이동할 보드 만들기
board = [([0] * n) for _ in range(n)]

# 사과의 위치 입력받기
apple = []
k = int(input())
for _ in range(k):
  input_row, input_col = map(int, input().split())
  # 문제에서 나온 맨위 맨 좌측 (1, 1)을 보드에서는 (0, 0)으로 위치 변환 
  apple_row, apple_col = input_row - 1, input_col - 1
  # 사과 위치를 나타내는 1을 보드에 표시
  board[apple_row][apple_col] = 1
  # 사과 리스트에 사과의 위치 좌표 추가
  apple.append((apple_row, apple_col))

# 뱀의 방향 회전 정보 입력받기
L = int(input())
change_snake = []
for _ in range(L):
  # 뱀의 방향 회전 정보를 리스트에 추가
  dis, direct = input().split()
  dis = int(dis)
  change_snake.append((dis, direct))

# 문제에서 주어진 시간은 10000초 이하로 해결
change_snake.append((10001, ''))

# 뱀의 북, 동, 남, 서 위치이동
change = [(-1, 0), (0, 1), (1, 0), (0, -1)]

# 뱀의 방향 전환
def turn_snake(direction):
  global turn_index
  # 왼쪽 방향으로 회전
  if direction == 'L':
    if turn_index != 0:
      turn_index -= 1
    else:
      turn_index = 3
  # 오른쪽 방향으로 회전
  else:
    if turn_index != 3:
      turn_index += 1
    else:
      turn_index = 0
  return

# 게임 전 뱀이 있는 위치
snake = deque()
snake.append((0, 0))

# 게임시작 시 뱀의 시작방향 동쪽
turn_index = 1

# 뱀의 머리 위치
x, y = 0, 0

# 게임 진행시간
cnt = 0
# 방향을 바꿀 때 출발 시간
start = 1

# 반복문 탈출 명령
breaker = False

# 뱀의 방향 정보를 입력받아
for i in range(len(change_snake)): 
  # 게임 시작
  start = cnt + 1
  for _ in range(start, change_snake[i][0]+ 1):
    # 이동할 좌표 설정
    nx = x + change[turn_index][0]
    ny = y + change[turn_index][1]
    # 이동할 좌표가 벽 또는 자기자신의 몸과 부딪힌다면 반복문 종료
    if nx < 0 or nx >= n or ny < 0 or ny >= n or (nx, ny) in snake:
      cnt += 1
      breaker = True
      break
    # 뱀이 이동할 다음 위치에 사과가 있다면
    if board[nx][ny] == 1:
    # 사과 먹기
      board[nx][ny] = 0
      x, y = nx, ny
      # 뱀의 위치 표시
      snake.append((x, y))
    # 다음 위치에 사과가 없다면
    else:
      x, y = nx, ny
      # 뱀의 위치 표시
      snake.popleft()
      snake.append((x, y))
    # 게임 1초씩 증가
    cnt += 1
  if breaker == True:
    break
  # 뱀 이동후 방향 전환
  turn_snake(change_snake[i][1])  

# 정답 출력
print(cnt)

 

 

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

3190번: 뱀

해답1 참고 : https://velog.io/@ms269/%EB%B0%B1%EC%A4%80-3190-%EB%B1%80-%ED%8C%8C%EC%9D%B4%EC%8D%AC-Python

[백준] #3190 - 뱀 (파이썬, Python)

해답2 참고 : https://data-flower.tistory.com/65

[백준 3190번] 뱀 - 파이썬