https://www.acmicpc.net/problem/3190
(아직 푸는 중이다)
처음 문제를 보고 머리가 아픈 지점은 뱀의 움직임을 구현하는 부분을 어떻게 만들어야 하지 였다 (이런 종류의 게임은 해봤지만... 움직임을 신경쓰지 않았어서)
문제에서 뱀의 움직임에 대한 문장을 보고 이해조차 되지 않았다
- (생각 과정)
벽과 자기자신을 만나면 죽으니 조건문을 만들고 그 안에서 움직임을 반복하게 해야겠네
일단 길이가 1로 시작하니 머리이자 몸이겠구니, 처음 위치는 맨 위 맨 좌측
처음에 오른쪽으로 이동
제일 이해가 가지 않았던 문장 2개
""먼저 뱀은 몸길이를 늘려 머리를 다음 칸에 위치시킨다""였다
: 1초 마다 몸길이가 늘어난다는 건가? 아니면 그저 뱀의 움직임을 설명한건가... 일단 패스
""만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.""
: 몸길이를 줄여 꼬리가 위치한 칸을 비워주는데 몸길이는 변하지 않는다고? (꼬리 칸을 비워주면 몸길이 자체는 변하지 않기야 하겠지만, 맨 뒤칸이 꼬리가 되는거 아닌가 그러면 결국에 몸길이도 변하는 거 아닌가?)
그리고 방향 전환이 없으면 그 방향 그대로 진행하는 것인가..?
사과가 시작하고 바로 있지 않으면 뱀은 없어지는 거 아닌가?
(게임이 끝나는 조건은 따로 있었으니 이것도 일단 패스)
패스 할 수 없는 조건들 이었다
https://www.youtube.com/watch?v=6lD3GPJp69U
움직임을 대강이라도 머릿속에 상상할 수 없어서 이후 진행이 불가능해 유튜브에 해설 강의를 보았는데 (다 보지 않고 4분대 에서 뱀의 움직임을 설명한 부분을 보고 움직임이 바로 이해가 가서 멈추고 다시 도전했다.)
일단 뱀은 방향 전환이 없으면 초마다 그대로 진행한다.
(임시로) 몸의 길이가 늘어가고 사과가 없다면 꼬리는 지워진다. 따라서 몸은 길이는 변화가 없다.
사과가 있디면, 꼬리는 비워지지 않고 사과가 있던 칸이 뱀의 머리가 된다.
이해가 되고 나니 쪽팔린다.. 이걸 이해 못 해서 전전긍긍했다니 조금만 픽셀 게임을 생각해봐도 뱀의 몸 길이는 그대로인데...
- 세팅(입력값 이용 및 시작 뱀의 위치)
은 일단 주어진 크키만큼의 리스트 컴프리헨션으로 이중 리스트로 배열을 만들어서 뱀이 움직일 수 있는 필드를 만들어주고 사과의 개수 만큼 for문을 돌려 그 만큼의 사과 개수와 위치를 입력받고 필드(뱀이 움직이는)에 1로 넣어줘서 사과를 의미하게 했다
그리고 방향 전환 정보는 딕셔너리로 저장해서 나중에 써먹을 수 있게 했다
N = int(input())
K = int(input())
field = [[0] * N for _ in range(N)]
for _ in range(K):
apple_row, apple_column = map(int, input().split())
field[apple_row - 1][apple_column - 1] = 1
direction_changenumber = int(input())
times = {}
for _ in range(direction_changenumber):
a, b = input.split()
times[int(a)] = b
dy = [-1, 0, 1, 0]
dx = [0, 1, 0 , -1]
destination = 1
time = 1
y, x = 0, 0
field[y][x] = 2 # 뱀의 초기 위치
snake = ??????을 해결하기 위해
뱀을 어떤 자료구조를 활용해서 표현해야 시간 복잡도를 맞추고 편하게 코드를 짤 수 있을까?
매 움직임에 (임시로)몸을 늘린 후 사과가 있으면 뱀은 길어지고 (뱀의 꼬리는 그대로이고) 없다면 꼬리는 지워진다.
즉, 꼬리는 지워졌다 사라졌다 한다
(회전은 나중에 생각하고) 경계선 나가면 안 되고 자기 몸을 자기가 물면 안 되고
몸이 늘어나서 사과가 있으면 늘어난대로 고정이고 없으면 사라짐
field[y][x] = 2 # 뱀의 초기 위치
뱀이 지나가는 곳마다 2로 표기한다면 뱀의 머리가 지나는 곳은 모두 2로 표기된다 사과가 있다 그러면 머리의 순서가 변한다라고 생각하는게 이해가 빨랐다
사과가 없다 순서가 변해 꼬리다 되어버린 머리가 잘리고 새로운 머리를 넣어준다
결론은
머리의 선입선출 > 큐 > deque 사용 (훨씬 편힘)
코드 상단에 from collections import deque를 하고
??? 부분을 snake = deque([[y,x]])로 바꿔주자 (후에 리스트 언패킹으로 값을 할당하기 위함이다)
<뱀의 움직임>
문제에서 제시된 문장의 뱀의 움직임은 이해했으니 코드로 풀어내자
일단 뱀의 움직임이 필드는 넘어가지 말아야 하고 뱀이 자신의 몸과 부딫히면 안 된다
몇 초에 정확히 끝나는지를 알아야 하니 그에 대한 계산식을 만들어야 하는데 필드는 각 입력마다 다르니 뱀이 지나간 곳들을 2로 표시해주고 반복시키다 2를 만나거나 뱀이 너무 길어져 필드 밖으로 나가면 멈추겠지
def direction_change(direction,char) :
if char == "C":
direction = (d -1) % 4
else:
direction = (d + 1) % 4
while True:
y, x = y + dy[direction], x + dx[direction]
if 0 <= y < N and 0 <= x < N and field[y][x] != 2 :
if not filed[y][x] == 1 :
del_y, del_x = snake.popleft()
field[del_y][del_x] = 0
filed[y][x] = 2
snake.append([y,x]) # 새로운 머리 넣어주기
#방향 전환 고려
if time in times.keys():
direction = direction_change(direction, times[time])
time += 1
else :
break;
print(time)풀 버전
from collections import deque
def direction_change(d,c):
if c == "L":
d = (d-1) % 4
if c == "D":
d = (d + 1) % 4
return d
N = int(input())
K = int(input())
field = [[0] * N for _ in range(N)]
for _ in range(K):
apple_row, apple_column = map(int, input().split())
field[apple_row - 1][apple_column - 1] = 1
direction_changeCount = int(input())
times = {}
for _ in range(direction_changeCount):
a, b = input().split()
times[int(a)] = b
dy = [-1, 0, 1, 0]
dx = [0, 1, 0 , -1]
direction = 1
time = 1
y, x = 0, 0
field[y][x] = 2 # 뱀 있는 곳을 2로 지정
snake = deque([[y,x]])
while True:
y, x = y + dy[direction], x + dx[direction]
if 0 <= y < N and 0 <= x < N and field[y][x] != 2 :
if not field[y][x] == 1:
del_y, del_x = snake.popleft()
field[del_y][del_x] = 0
field[y][x] = 2
snake.append([y,x])
if time in times.keys():
direction = direction_change(direction, times[time])
time += 1
else:
break
print(time)
