[Python] 백준 3190번 뱀
안녕하세요 (‾◡◝) ..
블로그 진짜 오랜만에 쓰는 것 같네요 ㅎㅎ
n개월 간 잠시 잊고 지냈던 백준을 오랜만에 꺼내보았습니다.
저는 메인 언어로 C를 쓰고 있었는데,
요즘은 python이나 C++을 제대로 공부해볼까 고민 중입니다.
코딩 테스트에서는 두 언어를 많이 쓴다고 하더라구요 -
서론이 길었네요!
암튼 오늘은 python을 사용하여
삼성 SW 역량 테스트 기출문제인 백준 3190번 문제를 풀어보았습니다.
3190번: 뱀
'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임
www.acmicpc.net
이번 문제도 역시 시뮬레이션 문제입니다!
조건이 여러 가지 주어졌지만, 하나하나 순서대로 구현하면 쉽게 해결할 수 있습니다.
저는 총 4단계에 걸쳐 코드를 구현하였습니다.
1. 보드의 상태 구분하기
저는 입력받은 값들 바탕으로 보드의 상태를 구분해주었습니다.
- 벽의 경우에는 -1
- 비어있는 경우에는 0
- 사과가 있는 경우에는 1
- 뱀이 있는 경우에는 2
벽의 경우에는 입력 받은 보드 배열의 상하좌우에 값을 추가해주었습니다.
예를 들어 보드의 크기인 N이 3이고 모든 보드가 비어있다면,
-1 -1 -1 -1 -1
-1 0 0 0 -1
-1 0 0 0 -1
-1 0 0 0 -1
-1 -1 -1 -1 -1
위와 같이 벽을 설정할 수 있습니다.
이렇게 설정하기 위해서는 전체 보드 배열의 행과 열 크기를 N+2로 잡아야 합니다.
2. 다음 칸으로 이동하기
이동을 구현하기 위해서는 우선 고려해야 할 사항이 있습니다.
바로 이동하는 방향에 대한 값입니다.
이동하는 방향에 따라 다음 칸을 의미하는 좌표값이 달라지기 때문입니다.
초기에는 뱀이 오른쪽을 향하도록 설정되어 있지만,
입력으로 들어온 뱀의 방향 변환 정보에 의해 뱀이 이동하는 방향이 바뀔 수 있습니다.
저는 direction이라는 변수를 사용하여 현재 뱀의 이동 방향을 저장해주었습니다.
- 오른쪽을 향한다면 direction = 0
- 아래를 향한다면 direction = 1
- 왼쪽을 향한다면 direction = 2
- 위쪽을 향한다면 direction = 3
이후 아래의 사진과 같이 direction 변수 값을 바탕으로 다음 칸으로 이동시켜 줍니다.
- direction이 0이라면 y += 1
- direction이 1이라면 x += 1
- direction이 2라면 y -= 1
- direction이 3이라면 x -= 1
이동을 끝내면 뱀의 정보를 저장시켜 줍니다.
이 정보를 저장해야 하는 이유는
'이동한 칸에 사과가 없다면 꼬리가 위치한 칸을 비운다'라는 조건 때문입니다.
뱀의 길이가 늘어날 때마다 새롭게 늘어간 좌표의 정보를 저장하고,
뱀의 꼬리 좌표가 필요할 때는 가장 먼저 저장되어 있는 값을 사용하면 됩니다.
이를 위해서는 큐를 사용할 수 있습니다. (First In First Out)
이동을 끝내면 시간을 증가시켜 줍니다. (뱀은 매 초마다 이동을 하기 때문)
3. 이동한 칸 확인하기
이동을 완료하였으면 이동한 칸의 보드 배열 값을 확인합니다.
- 배열 값이 벽(-1)이라면, 종료
- 배열 값이 비어있다면(0), 꼬리가 위치한 배열 비우기 + 현재 칸에 뱀 위치시키기
- 배열 값이 사과(1)라면, 현재 칸에 뱀 위치시키기
- 배열 값이 뱀(2)이라면, 종료
저는 무한루프를 돌리고 3번 단계에서 종료 조건을 설정해주었습니다.
꼬리가 위치한 배열을 비우기 위해서는 dequeue를 해주고,
반환받은 값의 보드 배열 값을 비어있음(0)으로 변경하였습니다.
현재 칸에 뱀을 위치시키기 위해서는 현재 좌표의 배열 값을 뱀(2)으로 설정하였습니다.
4. 방향 변환 정보 확인하기
방향 전환을 실시할 때 역시 현재 방향에 대한 고려를 해주어야 합니다.
위와 같이 현재 방향에 따라 왼쪽/오른쪽으로 회전시켰을 때 방향이 달라지기 때문입니다.
[
[3, 1], # direction = 0
[0, 2], # direction = 1
[1, 3], # direction = 2
[2, 0] # direction = 3
]저는 위와 같은 2차원 배열을 사용하여 방향 변환을 처리해주었습니다.
행은 현재 방향을 의미하며,
0열은 왼쪽으로, 1열은 오른쪽으로 회전시켰을 때의 direction 값을 의미합니다.
예를 들어 현재 direction 값이 1이고 오른쪽으로 회전을 시킨다면
1행 1열에 해당하는 2가 변환된 direction 값이 됩니다!
아래는 위의 4가지 단계를 거쳐 제가 구현한 코드입니다!
코드는 while 문을 중점적으로 확인하면 될 것 같습니다.
import queue
q = queue.Queue()
n = int(input())
k = int(input())
# 벽은 -1, 비어 있으면 0, 사과가 있으면 1, 뱀이 있으면 2
board = [[0 for _ in range(n+2)] for row in range(n+2)]
for i in range(n+2):
for j in range(n+2):
if i == 0 or i == n+1:
board[i][j] = -1
elif j == 0 or j == n+1:
board[i][j] = -1
# 사과가 있는 칸 입력 받기
for _ in range(k):
a, b = input().split()
board[int(a)][int(b)] = 1
# 방향 변환 정보 입력 받기
l = int(input())
info = {}
for _ in range(l):
x, c = input().split()
info[int(x)] = c
direction = 0 # 이동 방향
second = 0 # 시간
# 뱀의 초기값 설정
x = 1
y = 1
board[x][y] = 2
q.put([x, y])
def check(): # 이동한 칸 check
global x
global y
if board[x][y] == -1: # 이동한 칸에 벽
return 0
elif board[x][y] == 2: # 이동한 칸에 뱀
return 0
elif board[x][y] == 1: # 이동한 칸에 사과
return 1
return 2 # 이동할 칸이 비어있음
def move(): # 이동하기
global x
global y
if direction == 0: # 오른쪽으로
y += 1
elif direction == 1: # 아래쪽으로
x += 1
elif direction == 2: # 왼쪽으로
y -= 1
else: # 위쪽으로
x -= 1
def tail(): # 꼬리 비우기
global q
last = q.get()
board[last[0]][last[1]] = 0
def change(): # 방향 바꾸기
global second
global direction
direction_list = [[3, 1], [0, 2], [1, 3], [2, 0]] # [왼, 오]
if info[second] == 'L': # 왼쪽
direction = direction_list[direction][0]
else: # 오른쪽
direction = direction_list[direction][1]
while 1:
move()
q.put([x, y])
second += 1
checked = check()
if checked == 0: # 종료 조건
break
elif checked == 2: # empty
tail()
board[x][y] = 2
if second in info:
change()
print(second)
저는 python을 제대로 배워본 적이 없어서, (야매로만 써본)
코드를 간결하고 깔끔하게 짜는 게 좀 힘들더라구요 ㅠㅠ
python에서 제공하는 기능들에 좀 더 익숙해져야 할 것 같습니다.
문제를 좀 더 많이 풀어보는 걸로 ... ☆