뱀 (백준3190골드4삼성 SW기출)
메모
처음 뱀 길이 : 1
처음 뱀 위치 : 맨위 맨왼쪽
처음 뱀 이동 방향 : 오른쪽으로
1초(step)에 한 칸씩 이동
-
규칙
- 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.(깔짝 이동)
- 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. (토마토/바이러스 문제처럼 증가)
- 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다. (한칸 이동)
-
목표 : 몇 초에 끝나는지 구하라
-
테스트케이스 알아야할 점
- 방향 전환 시에는 앞으로 안나감
- 벽을 나가게 되면 그때 +1한 시간이 최종 답! (나가는 순간에 return cnt )
- 벽을 나가지 않고 끝까지 간 경우에도 그 마지막에 return cnt
알고리즘
나동빈 코드임
테스트케이스 이해 설명
-
case 1
-
case 2
-
case 3
솔루션 코드 - 나동빈
n = int(input())
k = int(input())
data = [[0] * (n + 1) for _ in range(n + 1)] # 맵 정보
info = [] # 방향 회전 정보
# 맵 정보(사과 있는 곳은 1로 표시)
for _ in range(k):
a, b = map(int, input().split())
data[a][b] = 1
# 방향 회전 정보 입력
l = int(input())
for _ in range(l):
x, c = input().split()
info.append((int(x), c))
# 처음에는 오른쪽을 보고 있으므로(동, 남, 서, 북)
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
def turn(direction, c):
if c == "L":
direction = (direction - 1) % 4
else:
direction = (direction + 1) % 4
return direction
def simulate():
x, y = 1, 1 # 뱀의 머리 위치
data[x][y] = 2 # 뱀이 존재하는 위치는 2로 표시
direction = 0 # 처음에는 동쪽을 보고 있음
time = 0 # 시작한 뒤에 지난 '초' 시간
index = 0 # 다음에 회전할 정보
q = [(x, y)] # 뱀이 차지하고 있는 위치 정보(꼬리가 앞쪽)
while True:
nx = x + dx[direction]
ny = y + dy[direction]
# 맵 범위 안에 있고, 뱀의 몸통이 없는 위치라면
if 1 <= nx and nx <= n and 1 <= ny and ny <= n and data[nx][ny] != 2:
# 사과가 없다면 이동 후에 꼬리 제거
if data[nx][ny] == 0:
data[nx][ny] = 2
q.append((nx, ny))
px, py = q.pop(0)
data[px][py] = 0
# 사과가 있다면 이동 후에 꼬리 그대로 두기
if data[nx][ny] == 1:
data[nx][ny] = 2
q.append((nx, ny))
# 벽이나 뱀의 몸통과 부딪혔다면
else:
time += 1
break
x, y = nx, ny # 다음 위치로 머리를 이동
time += 1
if index < l and time == info[index][0]: # 회전할 시간인 경우 회전
direction = turn(direction, info[index][1])
index += 1
return time
print(simulate())- 필기하면서 본거 (답이 틀리게 나옴...?)
n = int(input())
k = int(input())
data = [[0] * (n+1) for _ in range(n+1)] # 문제의 인덱스 1부터니까
info = [] # 방향 회전 정보
#맵 정보 (사과가 있는 곳을 1로 표시)
for _ in range(k):
A, B = map(int, input().split())
data[A][B] = 1
# 방향 회전 정보 입력 (L은 총 회전하는 횟수가 된다)
L = int(input())
for _ in range(L):
x, c = input().split()
info.append((int(x), c)) # 튜플로 묶어서 넣어줌
# 뱀이 회전할 때 방향 틀어주는 함수
def turn(direction, c):
if c == 'L':
direction = (direction -1) % 4
else:
direction = (direction +1) % 4
return direction
# (중요) 처음엔 오른쪽을 보기 때문에 오른쪽 봤을 때를 기준으로 상하좌우임 <아래, 우, 위, 좌>
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]
def simulate():
x, y = 1, 1 # 뱀의 머리 위치
data[x][y] = 2 # 뱀이 존재하는 위치는 2로 표시할거임 (사과먹으면 ++이므로)
direction = 0 # 처음에는 오른쪽을 보고 있음
time = 0
index = 0 # 현재 뱀이 회전한 횟수
q = [(x, y)] # 뱀이 차지하고 있는 위치 정보 (꼬리가 앞쪽)
while True:
# "지정해둔 방향으로!!!" 한칸 이동
nx = x + dx[direction]
ny = y + dy[direction]
# 맨날 하던거, 범위 내에서 움직이도록! 그리고 뱀 몸 안만지도록!!
if 1 <= nx and nx <= n and 1 <= ny and ny <= n and data[nx][ny] != 2:
# 사과 없는 경우 -> 이동 후 꼬리 제거
if data[nx][ny] == 0:
# 이동 후 위치도 갱신
data[nx][ny] = 2
q.append((nx,ny))
# 이전 위치는 0으로
px, py = q.pop(0)
data[px][py] = 0
# 사과 있는 경우 -> 머리만 늘리기
if data[nx][ny] == 1:
data[nx][ny] = 2
q.append((nx,ny))
# 벽에 부딪히는 경우 or 뱀 몸에 부딪히는 경우
else:
time += 1 # 이동은 한거니까 ++ 해주고
break
# (여기부터 중요!!) 다음 위치로 머리 이동
x, y = nx, ny
time += 1
# 회전 수행 -> 회전 횟수가 남았고, 시간이 회전할 시간이 되었다면 (= [index][0])
if index < L and time == info[index][0]:
# 방향 틀어
direction = turn(direction, info[index][1])
index += 1
# 어디 안부딪히고 정상마무리하는 경우
return time
print(simulate())
Do My Best