문제
[골드 4] https://www.acmicpc.net/problem/3190
문제 유형 : 구현(시뮬레이션), 덱
해설 없이 스스로 풀었나요?
O
예제 출력 방향 전환을 이상하게 해서 문제 이해하는 데 시간이 너무 오래 걸렸다.
뱀의 이동을 큐로 구현해야 된다는 깨달음을 조금 더 일찍 얻었다면 ..
행 열 ny nx를 한 부분에서 반대로 써서 틀리고 있었따..
아이디어
이 문제의 포인트는 뱀이 이동하는 좌표를 큐에 넣는 것이다.
뱀이 이동하며 꼬리는 자르고(popleft), 머리는 이동한 새로운 좌표를 추가(append)한다.
(필자는 큐를 생각 못하고.. 구현하다가, 뱀이 회전 하는데 꼬리의 좌표를 어떻게 자르지.. 하고 고민 중 큐라는 자료구조가 번뜩였다.)
풀이과정
- 그래프를 모두 0으로 채운다.
- 사과의 위치는 2로 채운다.
- 이후 뱀이 차지하고 있는 부분은 1로 채운다.
4-1. 뱀이 이동할 때마다 머리와 꼬리는 한 칸씩 전진한다. (몸의 길이는 변하지 않는다.)
4-2. 뱀이 이동했을 때 사과를 먹으면 머리는 전진하지만 꼬리는 그대로이다. (몸의 길이가 한 칸 늘어난다.)
사과를 먹으면 그 위치는 1로 바꾼다. (사과는 없어지고 뱀이 위치하기 때문) - 방향 전환을 해야 하는 타이밍이면, L은 왼쪽, D는 오른쪽으로 방향 전환한다.
- 뱀이 이동했을 때 벽에 부딪히거나, 자기 자신에 부딪히면 종료한다.
먼저, 1, 2, 3은 그대로 구현할 수 있다.
4-1 위에서 언급한 대로 큐 자료형을 이용한다.
처음 시작할 때의 위치 (0,0)을 큐에 넣어 몸길이 1인 뱀의 초기 상태를 저장한다.
이후 오른쪽으로 한 칸 이동하면 (0,0)을 큐에서 pop하고, (0,1)을 큐에 push하여 뱀의 위치 상태를 변경한다.
즉, 큐가 뱀의 몸을 나타낸다고 생각하면 된다.
4-2 그래프에 사과가 있는 경우, 즉 board[y][x] == 2인 경우에는 뱀의 머리만 전진하므로 큐에서 pop하지 않고, 전진하여 머리가 있는 위치를 큐에 push하여 뱀의 몸 길이를 늘려준다.
5 방향 전환
나는 노가다로 케이스를 나누어서 구현했는데 오른쪽으로 방향 전환, 왼쪽으로 방향 전환이 '회전' 을 나타내는 것이었다.
오른쪽 전환('D')이 시계방향, 왼쪽 전환('L')이 반시계방향을 뜻한다.
그리고 상하좌우 이동에서, 상(0), 우(1), 하(2), 좌(3)이라고 하면
- 시계방향(D) : 상 - 우 - 하 - 좌 - 상 순으로 바뀜 (+1)
- 반시계방향(L) : 상 - 좌 - 하 - 우 - 상 순으로 바뀜 (-1)
즉, 현재 방향 상태를 숫자로 표현하고, 그다음 바뀌게 될 방향을 주어진 방향 전환 조건에 맞게 +1 또는 -1 해주면 된다.
추가로, 방향을 바꾸어야 할 시간인지 입력받은 부분을 딕셔너리에 저장한다.
키 / 밸류 를 각각 시간 / 방향으로 저장한다.
반복문을 돌 때마다 딕셔너리를 확인하며 현재 시간이 딕셔너리에 키 값으로 있는지 없는지 확인하고, 있다면 direction을 위의 회전에 따라 갱신해주도록 한다.
6 이동 가능 확인
벽에 부딪히거나, 자기 자신의 몸과 부딪히면 이동할 수 없으므로 반복을 종료한다.
x < 0 or x >= N or y < 0 or y >= N 이면 벽에 부딪히고
board[y][x] == 1 이면 해당 위치에 뱀의 몸이 있다는 뜻이므로 그 좌표로 이동하면 자신의 몸과 부딪힌다.
위의 조건이 아닌 경우에 대해서만 반복한다.
풀이
1. 구글링 후 리팩토링 한 코드
from collections import deque
N = int(input())
K = int(input())
board = [[0] * N for _ in range(N)]
for _ in range(K):
i, j = map(int, input().split())
board[i-1][j-1] = 2 # 행열 인덱스 -1씩 해줘야 함, 사과의 위치 2로 표현
direction_dict = {}
L = int(input())
for _ in range(L):
a, b = input().split()
direction_dict[int(a)] = b
# 상(0), 우(1), 하(2), 좌(3) 이동 : graph[ny][nx] 기준
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
direction = 1 # 처음 뱀 이동방향은 오른쪽
time = 0 # 게임 시간
board[0][0] = 1 # 처음 뱀의 위치 1로 표현
nx, ny = 0, 0 # 뱀의 머리 위치
q = deque()
q.append((ny, nx))
def change(d, c):
if c == 'D':
d = (d + 1) % 4
else: # c == 'L':
d = (d - 1) % 4
return d
while True:
time += 1
nx = nx + dx[direction]
ny = ny + dy[direction]
if nx < 0 or nx >= N or ny < 0 or ny >= N:
break
if board[ny][nx] == 1:
break
elif board[ny][nx] == 2: # 사과가 있다면
# board[ny][nx] = 0 # 사과 없애고
board[ny][nx] = 1
q.append((ny, nx))
elif board[ny][nx] == 0: # 사과가 없다면
ey, ex = q.popleft()
board[ey][ex] = 0 # 꼬리 자리는 다시 0으로
board[ny][nx] = 1
q.append((ny, nx))
if time in direction_dict.keys():
direction = change(direction, direction_dict[time]) # <- 키 값을 통해 벨류 값 구하고(d인지 l인지) 같이 인자 전달)
# print(q, time, direction)
print(time)2. 내가 짠 코드(정답이긴 합니다..^^)
다만 필요없는 변수도 있고, 노가다 구현 부분이 있어 윗코드를 참고해주세요.
from collections import deque
N = int(input())
K = int(input())
board = [[0] * N for _ in range(N)]
for _ in range(K):
i, j = map(int, input().split())
board[i-1][j-1] = 2 # 행열 인덱스 -1씩 해줘야 함, 사과의 위치 2로 표현
change = []
L = int(input())
for _ in range(L):
a, b = input().split()
change.append((int(a), b))
time = 0 # 게임 시간
size = 1 # 뱀 크기
board[0][0] = 1 # 처음 뱀의 위치 1로 표현
# 순서대로 좌 우 하 상 이동 : graph[ny][nx] 기준
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# case 1 : 좌, 2 : 우, 3 : 하, 4 : 상 이동
direction = 2 # 처음 뱀 이동방향은 오른쪽
nx, ny = 0, 0 # 뱀의 머리 위치 - 따로 표기할 필요가 있을까? 그냥 그래프에서 값을 1이 아닌 다른 값으로 해도 될 것 같음
ex, ey = nx, ny # 뱀의 꼬치 위치 - 처음에는 모두 0
change_time = 0
q = deque()
q.append((ny, nx))
while True:
# 뱀이 자기자신과 부딪히거나 벽에 부딪히는 경우 break, 그때의 게임 초 return
# 자기자신과 부딪힘 = 머리가 이동한 곳이 이미 값이 1이다.
time += 1
nx = nx + dx[direction - 1]
ny = ny + dy[direction - 1]
# print(nx, ny)
if nx < 0 or nx >= N or ny < 0 or ny >= N:
break
if board[ny][nx] == 1:
break
elif board[ny][nx] == 2: # 사과가 있다면
board[ny][nx] = 0 # 사과 없애고
size += 1
board[ny][nx] = 1
q.append((ny, nx))
elif board[ny][nx] == 0: # 사과가 없다면 <- ㅋㅋ.. nx ny로 씀..
ey, ex = q.popleft()
board[ey][ex] = 0 # 꼬리 자리는 다시 0으로
board[ny][nx] = 1
q.append((ny, nx))
# print(q, time, size)
for i in range(change_time, L):
if time == change[i][0]:
if change[i][1] == 'L': # 좌
if direction == 1: direction = 4
elif direction == 2: direction = 3
elif direction == 3: direction = 1
elif direction == 4: direction = 2
if change[i][1] == 'D': # 우
if direction == 1: direction = 3
elif direction == 2: direction = 4
elif direction == 3: direction = 2
elif direction == 4: direction = 1
change_time += 1
# print(direction)
print(time)Comment
다음 문제는 무엇을 풀까요
