[BOJ] 3190 뱀 - 삼성 SW 역량 테스트 기출
https://www.acmicpc.net/problem/3190
문제 요약
- 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
- 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
- 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
- 사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.
접근방법
1. 뱀의 좌표 저장할 deque - 맨 앞값이 꼬리(제일 먼저 추가된 값이니까), 맨뒤값이 머리
2. bfs 돌면서 다음칸에 위치시킬 좌표,방향,시간 큐에 추가
-이때 방향전환할 시간이면 방향 전환(dy, dx 인덱스로 조절)
3. 가야될 위치에 사과 있으면 사과 먹고 머리좌표 추가하고 꼬리좌표 pop x
4. 사과 없으면 머리좌표만 추가하고 꼬리좌표 popleft
5. 다음 가야되는 지점이 벽이거나 이미 자기 몸이면 time 리턴
# BOJ 3190 뱀 [삼성 SW 역량 테스트 기출] - 김수민 (40분)
from collections import deque
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
def bfs():
while tmp:
y, x, time, dir = tmp.popleft()
ny = y + dy[dir]
nx = x + dx[dir]
# 벽에 부딪히거나 새로 이동할 곳에 자기 몸이 있으면 걸린 시간 리턴(이동 예정인 좌표니까 시간 + 1 해줌)
if ny < 0 or ny >= N or nx < 0 or nx >= N:
return time + 1
if ((ny, nx)) in snake:
return time + 1
# 방향이동시간이면 방향 바꿔준다. dy, dx가 시계방향 순서이므로 왼,오에 따라 인덱스 조절
if Q:
if time + 1 == int(Q[0][0]):
t, d = Q.popleft()
if d == 'D':
dir = (dir + 1) % 4
elif d == 'L':
dir = (dir + 3) % 4
snake.append((ny, nx)) # 뱀
if arr[ny][nx] != 1: # 사과 없으면
snake.popleft() # 꼬리떼기
elif arr[ny][nx] == 1: # 사과 먹으면
arr[ny][nx] = 0 # 사과부분 0으로
tmp.append((ny, nx, time + 1, dir))
N = int(input())
K = int(input())
arr = [[0] * N for _ in range(N)]
for k in range(K):
y, x = map(int, input().split())
arr[y-1][x-1] = 1
Q = deque() # 방향 전환
tmp = deque() # 새로 이동할 뱀의 머리 부분 (y좌표, x좌표, 시간, 방향) 담음
snake = deque() # 뱀의 몸에 해당되는 좌표 담음
L = int(input())
snake.append((0,0))
for l in range(L):
t, dir = input().split()
Q.append((t, dir))
tmp.append((0,0,0,0))
print(bfs())
Author And Source
이 문제에 관하여([BOJ] 3190 뱀 - 삼성 SW 역량 테스트 기출), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@smkim104/BOJ-3190-뱀-삼성-SW-역량-테스트-기출저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)