[백준 3190번] 뱀 - 파이썬

문제 링크:

 

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

3190번: 뱀

 

백준 3190번 뱀 문제는 삼성 SW 역량테스트 기출문제이다.

 

백준 3190 파이썬

 

---

풀이 유형:

구현, 자료구조, 시물레이션, 덱, 큐

 

풀이  과정: 

 

이 문제도 앞서 풀은 테트로미노와 마찬가지로 복잡한 구현을 하는 문제이다.

특히 사과를 먹으면 알아서 맵에서 지워줘야 하는 센스가 필요, 뱀의 형태를 담을 자료구조도 알아야 하는 문제이다. 

문제를 꼼꼼이 읽어야 주어진 조건을 놓치지 않는다.

1. 2차원 배열상의 맵에서 뱀이 이동하도록 해야 하므로 2차원 배열상의 특정 위치에서 동, 남, 서, 북의 위치로 이동하는 기능을 구현해야한다.

2. 뱀이 처음에 오른쪽(동쪽)을 바라보고 있다는 점 고려해야 한다.

3. 뱀의 머리가 뱀의 몸에 닿는 경우도 종료해야 하므로, 매 시점마다 뱀이 존재하는 위치를 항상 2차원 리스트에 기록해야 한다.

 

시물레이션 문제 꿀팁

시물레이션 문제 유형을 가장 쉽게 풀기 위해서는 그림을 그려보는 것이 좋다. 문제에서 주어진 예제 입력을 그대로 그림을 그려 나타내 보자.

필자는 예제 입력 2를 가지고 뱀의 머리 위치를 보드판에 그려보았다. 

예제입력2를 가지고 뱀의 머리 위치를 그림 그리기

 

사과의 위치에 따라 뱀이 있는 좌표가 달라짐을 알 수 있다. 여기서 사과를 안 먹었을 때 deque(덱)에 있는 popleft( )를 이용하여 맨 처음 원소가 빠지게 한 것이 중요하다.

사과를 안 먹었을 때 뱀의 위치가 (0, 0) 소거되고 (0, 5)가 추가되었다.

사과의 유무에 따라 뱀의 위치값이 달라진다

 

필자는 문제를 풀 때 문제의 조건들을 충실히 구현하였지만, for 이중 구문을 탈출시키는 방법에 대해 미숙해 잠시 헤맸다;;

(참고로 이 문제를 풀은 다른 분들의 해설을 보면 while 구문으로 많이 풀었다)

이번 문제를 계기로 for 이중구문을 탈출시키는 방법을 새로이 알게 되었다.

안쪽에 있는 for 구문에 breaker = True를 설정해주고, 바깥쪽에 있는 for구문에 breaker = True일 시 break를 해주면 된다. 밑에 코드를 살펴보면서 어떻게 이중구문 for 구문을 탈출하는지 확인할 수 있다.

 

다음 풀이 코드는 필자가 스스로 작성한 것이다.

 

풀이 코드:

 

# 3190번 뱀

from collections import deque

# 보드의 크기 입력받기
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)

 

 

3190번 뱀