미소를뿌리는감자의 코딩
[백준 2024/09/11] 3190번 뱀 본문
728x90
1. 문제
https://www.acmicpc.net/problem/3190
2. 접근 방법
이번 문제는 tail이 따라가야 할 방향과 회전 방향을 어떻게 처리하느냐가 중요한 것 같다.
이들을 queue로 구현하여, 구현 가능하도록 하였다.
방향 회전은 아래와 같이 구성하였다.
위와 같이 방향을 처리해 주었다.
head가 새로운 곳으로 이동하게 되면, 이를 tail_location 이라는 deque 에 뒤로 넣어주었다.
또한 deque.popleft()를 통해서 tail이 따라가야할 위치를 알아내 주었다.
이 외, 다른 부분은 직관적으로 구현하였다.
3. 코드
from collections import deque
head_location = [0, 0]
tail_location = deque()
tail_location.append([0, 0])
n = 0
snake_location = []
apples = []
queue_direction = deque([[0, 1], [1, 0], [0, -1], [-1, 0]])
def print_squares(n, square):
for i in range(n):
print(square[i])
print()
def place_apples(apple_num):
global apples, n
apples = [[0] * n for _ in range(n)]
for _ in range(apple_num):
i, j = map(int, input().split())
apples[i - 1][j - 1] = 1
return apples
def mark_directions(n):
directions = []
for _ in range(n):
s, d = input().split()
directions.append([int(s), d])
return directions
def go_straight(seconds, direction):
global head_location, tail_location, snake_location, apples, n
passed_seconds = 0
for i in range(seconds):
head_location = [head_location[0] + direction[0], head_location[1] + direction[1]]
passed_seconds += 1
tail_location.append(head_location)
if not (0 <= head_location[0] < n and 0 <= head_location[1] < n):
return False, passed_seconds
if snake_location[head_location[0]][head_location[1]] == 1:
return False, passed_seconds
snake_location[head_location[0]][head_location[1]] = 1
if not apples[head_location[0]][head_location[1]]:
x, y = tail_location.popleft()
snake_location[x][y] = 0
else:
apples[head_location[0]][head_location[1]] = 0
return True, seconds
def change_direction(lr):
global queue_direction
if lr == 'D':
queue_direction.append(queue_direction.popleft())
return queue_direction[0]
queue_direction.appendleft(queue_direction.pop())
return queue_direction[0]
def duration_game(directions):
global head_location, tail_location, snake_location, apples, n
seconds = 0
direction = [0, 1]
while directions:
next_s, next_d = directions.pop(0)
succeeded, passed_seconds = go_straight(next_s - seconds, direction)
if succeeded:
seconds += passed_seconds
direction = change_direction(next_d)
else:
seconds += passed_seconds
return seconds
succeeded, passed_seconds = go_straight(n+1, direction)
return seconds + passed_seconds
if __name__ == "__main__":
n = int(input())
snake_location = [[0] * n for _ in range(n)]
snake_location[0][0] = 1
apples = place_apples(int(input()))
directions = mark_directions(int(input()))
print(duration_game(directions))
아래 주석 처리된 부분을 풀고 보면,
뱀의 이동을 잘 파악할 수 있다.
from collections import deque
head_location = [0, 0]
tail_location = deque()
tail_location.append([0, 0])
n = 0
snake_location = []
apples = []
queue_direction = deque([[0, 1], [1, 0], [0, -1], [-1, 0]])
def print_squares(n, square):
for i in range(n):
print(square[i])
print()
def place_apples(apple_num):
global apples, n
apples = [[0] * n for _ in range(n)]
for _ in range(apple_num):
i, j = map(int, input().split())
apples[i - 1][j - 1] = 1
return apples
def mark_directions(n):
directions = []
for _ in range(n):
s, d = input().split()
directions.append([int(s), d])
return directions
def go_straight(seconds, direction):
global head_location, tail_location, snake_location, apples, n
passed_seconds = 0
#print("seconds")
#print(seconds)
#print()
for i in range(seconds):
head_location = [head_location[0] + direction[0], head_location[1] + direction[1]]
passed_seconds += 1
tail_location.append(head_location)
if not (0 <= head_location[0] < n and 0 <= head_location[1] < n):
return False, passed_seconds
if snake_location[head_location[0]][head_location[1]] == 1:
return False, passed_seconds
snake_location[head_location[0]][head_location[1]] = 1
if not apples[head_location[0]][head_location[1]]:
#print("tail_location")
#print(tail_location)
#print()
x, y = tail_location.popleft()
snake_location[x][y] = 0
else:
apples[head_location[0]][head_location[1]] = 0
#print("snake_location")
#print_squares(n, snake_location)
#print("apple_location")
#print_squares(n, apples)
#print("tail_location")
#print(tail_location)
#print()
#print("head_location")
#print(head_location)
#print()
#print("passed_seconds")
#print(passed_seconds)
return True, seconds
def change_direction(lr):
global queue_direction
if lr == 'D':
queue_direction.append(queue_direction.popleft())
return queue_direction[0]
queue_direction.appendleft(queue_direction.pop())
return queue_direction[0]
def duration_game(directions):
global head_location, tail_location, snake_location, apples, n
seconds = 0
direction = [0, 1]
while directions:
#print("directions: ", directions)
next_s, next_d = directions.pop(0)
#print("next_s:", next_s)
#print("next_d:", next_d)
succeeded, passed_seconds = go_straight(next_s - seconds, direction)
#print("succeeded:", succeeded)
#print("passed_seconds:", passed_seconds)
if succeeded:
seconds += passed_seconds
direction = change_direction(next_d)
else:
seconds += passed_seconds
return seconds
succeeded, passed_seconds = go_straight(n+1, direction)
return seconds + passed_seconds
if __name__ == "__main__":
n = int(input())
snake_location = [[0] * n for _ in range(n)]
snake_location[0][0] = 1
apples = place_apples(int(input()))
directions = mark_directions(int(input()))
print(duration_game(directions))
728x90
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/09/12] 13334번 철로 (0) | 2024.09.12 |
---|---|
[백준 2024/09/11] 1655번 가운데를 말해요 (0) | 2024.09.11 |
[백준 2024/09/11] 2504번 괄호의 값 (0) | 2024.09.11 |
[백준 2024/09/10] 2493번 탑 (0) | 2024.09.10 |
[백준 2024/09/10] 1629번 곱셈 (0) | 2024.09.10 |