https://www.acmicpc.net/problem/21611
21611번: 마법사 상어와 블리자드
마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, (
www.acmicpc.net
접근
먼저 맵에 설치된 벽에 의해 중앙에서 시작해서 토네이도처럼 탐색을 진행해야한다.
이를 위해 탐색하는 순서대로 맵에 표시를 하였다. 0부터 N*N - 1까지의 숫자로 탐색을 해야하는 순서를 정하고
순서대로 좌표를 기록해둔다.
이렇게하면 탐색하는 것이 편해진다.
이후 빈 칸을 채워서 이동하는 함수와 같은 숫자가 4개 이상 연속되었는지 판단하는 함수와 그룹 숫자를 만드는 함수를 구현하여 활용한다.
해당 문제의 핵심은 토네이도처럼 핵심하는 것을 어떻게 할 것인지였다고 생각한다.
또한 기능별로 함수를 구현 후에 문제를 해결했을 때 디버깅도 쉬웠다.
구현
- 중앙을 시작으로 토네이도처럼 탐색할 때 해당 순서를 order_pos에 저장한다.
- 이때 왼쪽 -> 아래 -> 오른쪽 -> 위 순서대로 방향이 진행되며
- 각각의 방향에서의 스텝은 1, 1, 2, 2, 3, 3 처럼 왼쪽과 오른쪽일 때 스텝이 증가한다.
def make_order_map():
y = N // 2
x = N // 2
order_pos.append((y, x))
dy = [0, 1, 0, -1]
dx = [-1, 0, 1, 0]
cd = 0
step = 0
while True:
if cd % 2 == 0:
step += 1
flag = True
for _ in range(step):
y += dy[cd]
x += dx[cd]
order_pos.append((y, x))
if y == 0 and x == 0:
flag = False
break
if not flag:
break
cd = (cd + 1) % 4- solve함수에서 M번의 마법이 시전된다.
- 각각 마법 시전 -> 빈 칸을 채우는 이동 -> 같은 숫자가 연속된 것이 4개인지 판단 -> 그룹 넘버 만들기
- 위의 순으로 진행되고 해당 기능을 함수로 구현했다.
def solve(board, m):
if m == M:
return
# 마법시전
D, S = cmd[m][0], cmd[m][1]
cy = cx = N//2
for s in range(1, S+1):
ny = cy + (s * dy[D])
nx = cx + (s * dx[D])
if check_range(ny, nx):
board[ny][nx] = 0
# 빈 칸 채우기
move_to_empty(board)
# 연속된 숫자가 4개 있는지
while find_4_numbers(board):
move_to_empty(board)
# 번호 그룹 만들기, 개수-번호 순
make_group(board)
solve(board, m+1)- 빈 칸을 채우는 함수이다.
- 빈 칸이 있을 때 큐로 선언한 move_pos에 좌표를 넣어주고
- 숫자를 만나면 move_pos에서 하나를 꺼내어 채워준다.
- 채워준뒤 원래 있던 자리는 빈 칸으로 만들고 move_pos에 넣어준다.
def move_to_empty(board):
move_pos = deque()
for y, x in order_pos:
if y == N//2 and x == N//2:
continue
if board[y][x] == 0:
move_pos.append((y, x))
elif board[y][x] > 0 and move_pos:
my, mx = move_pos.popleft()
board[my][mx], board[y][x] = board[y][x], 0
move_pos.append((y, x))- 이제 같은 숫자가 연속으로 4개가 나오는지 판단한다.
- 같은 숫자일 때 count를 증가시키고 visited에 좌표를 추가한다.
- 이후 다른 숫자가 나온 상황에서
- count가 4개 이상일 때 최종해를 구하기위해 점수를 기록해둔다.
- 만약 같은 숫자가 연속으로 4번 나오지 않는다면 false를 반환하도록 한다.
def find_4_numbers(board):
visited = deque()
count = 0
number = -1
flag = False
for y, x in order_pos:
if y == N//2 and x == N//2:
continue
if number == board[y][x]:
visited.append((y, x))
count += 1
else:
if count >= 4:
flag = True
scores[number] += count
while visited:
ny, nx = visited.popleft()
if count >= 4:
board[ny][nx] = 0
count = 1
number = board[y][x]
visited.append((y, x))
return flag- 마지막으로 해당 숫자가 몇 번나오는지 맵에 표시한다.
- 해당 숫자가 몇 번 나오는지와 수를 numbers에 순서대로 넣는다.
- 이후 order_pos의 순서대로 numbers의 0번 인덱스부터 채워준다.
def make_group(board):
number = -1
count = 0
numbers = [0]
for y, x in order_pos:
if y == N//2 and x == N//2:
continue
if number == -1:
number = board[y][x]
count = 1
else:
if number == board[y][x]:
count += 1
else:
numbers.append(count)
numbers.append(number)
number = board[y][x]
count = 1
idx = 0
for y, x in order_pos:
board[y][x] = numbers[idx]
idx += 1
if idx >= len(numbers):
break전체 코드
import sys
from _collections import deque
input = sys.stdin.readline
def check_range(y, x):
return (0 <= y < N) and (0 <= x < N)
def make_order_map():
y = N // 2
x = N // 2
order_pos.append((y, x))
dy = [0, 1, 0, -1]
dx = [-1, 0, 1, 0]
cd = 0
step = 0
while True:
if cd % 2 == 0:
step += 1
flag = True
for _ in range(step):
y += dy[cd]
x += dx[cd]
order_pos.append((y, x))
if y == 0 and x == 0:
flag = False
break
if not flag:
break
cd = (cd + 1) % 4
def move_to_empty(board):
move_pos = deque()
for y, x in order_pos:
if y == N//2 and x == N//2:
continue
if board[y][x] == 0:
move_pos.append((y, x))
elif board[y][x] > 0 and move_pos:
my, mx = move_pos.popleft()
board[my][mx], board[y][x] = board[y][x], 0
move_pos.append((y, x))
def find_4_numbers(board):
visited = deque()
count = 0
number = -1
flag = False
for y, x in order_pos:
if y == N//2 and x == N//2:
continue
if number == board[y][x]:
visited.append((y, x))
count += 1
else:
if count >= 4:
flag = True
scores[number] += count
while visited:
ny, nx = visited.popleft()
if count >= 4:
board[ny][nx] = 0
count = 1
number = board[y][x]
visited.append((y, x))
return flag
def make_group(board):
number = -1
count = 0
numbers = [0]
for y, x in order_pos:
if y == N//2 and x == N//2:
continue
if number == -1:
number = board[y][x]
count = 1
else:
if number == board[y][x]:
count += 1
else:
numbers.append(count)
numbers.append(number)
number = board[y][x]
count = 1
idx = 0
for y, x in order_pos:
board[y][x] = numbers[idx]
idx += 1
if idx >= len(numbers):
break
def solve(board, m):
if m == M:
return
# 마법시전
D, S = cmd[m][0], cmd[m][1]
cy = cx = N//2
for s in range(1, S+1):
ny = cy + (s * dy[D])
nx = cx + (s * dx[D])
if check_range(ny, nx):
board[ny][nx] = 0
# 빈 칸 채우기
move_to_empty(board)
# 연속된 숫자가 4개 있는지
while find_4_numbers(board):
move_to_empty(board)
# 번호 그룹 만들기, 개수-번호 순
make_group(board)
solve(board, m+1)
N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
order_pos = []
cmd = []
scores = [0, 0, 0, 0]
for _ in range(M):
d, s = map(int, input().split())
cmd.append((d, s))
make_order_map()
dy = [0, -1, 1, 0, 0]
dx = [0, 0, 0, -1, 1]
solve(board, 0)
answer = 0
for i in range(1, 4):
answer += (i*scores[i])
print(answer)'알고리즘 풀이 > 백준' 카테고리의 다른 글
| [백준 14621] 나만 안되는 연애 (0) | 2021.07.13 |
|---|---|
| [백준 16398] 행성 연결 (0) | 2021.07.13 |
| [백준 10423] 전기가 부족해 (0) | 2021.07.12 |
| [백준 21609] 상어 중학교 (0) | 2021.07.11 |
| [백준 21610] 마법사 상어와 비바라기 (0) | 2021.07.10 |