[BOJ]20056 마법사 상어와 파이어볼(Python) - 삼성SW역량테스트 기출
https://www.acmicpc.net/problem/20056
문제 요약
- 명령횟수만큼 주어진 방향, 속력으로 파이볼이 이동
- 한명령이 끝나고 겹쳐있는 파이어볼은 합쳐서 4개로 분할
- 질량은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋이다.
- 속력은 ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋이다.
- 합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 된다. - 1행과 N행, 1열과 N열은 연결되어 있다 -> 즉, 경계 벗어나는 거 없이 1행 넘어가면 N행으로, N행 넘어가면 1행으로
# 22056 마법사 상어와 파이어볼 [삼성SW역량테스트 기출- 구현] 골드5 - 김수민
from collections import deque
N, M, K = map(int, input().split())
Q = deque(); cnt = 0
# 방향이동
dy = [-1, -1, 0, 1, 1, 1, 0, -1]
dx = [0, 1, 1, 1, 0, -1, -1, -1]
for i in range(M):
y, x, m, s, d = map(int, input().split())
Q.append((y - 1, x - 1, m, s, d))
anw = 0
while cnt < K:
bomblist = deque() # 합쳐질 애들 좌표 후보
arr = [[[] for _ in range(N)] for _ in range(N)]
visit = [[1] * N for _ in range(N)]
hubo = [] # 합쳐지는 애들 말고 이동한 파이어볼들
while Q:
y, x, m, s, d = Q.popleft()
ny = y + dy[d] * s; nx = x + dx[d] * s
# 방향 조정(경계 넘어가면)
if ny >= N:
ny = ny % N
elif ny < 0:
while ny < 0:
ny = N + ny
if nx >= N:
nx = nx % N
elif nx < 0:
while nx < 0:
nx = N + nx
# 이미 담겨져있으면(합쳐야 됨)
if arr[ny][nx]:
yy, xx, mm, ss, dd = arr[ny][nx].pop()
mm += m; ss += s
# 짝수, 홀수 방향이 섞여 있으면
if (dd % 2 and d % 2 == 0) or (dd % 2==0 and d % 2 == 1):
dd = -1
arr[ny][nx].append((yy,xx,mm,ss,dd))
visit[ny][nx] += 1
# 합쳐질 애들에 이미 포함돼있으면 통과
if visit[ny][nx] <= 2:
bomblist.append((ny, nx))
else:
hubo.append((ny, nx, m, s, d))
arr[ny][nx].append((ny, nx, m, s, d))
# 합쳐질 애들에 포함 안됐고 후보이면
for idx in range(len(hubo)):
y, x, m, s, d = hubo[idx]
if visit[y][x] == 1:
Q.append((y, x, m, s, d))
# 합칠 애들
for idx in range(len(bomblist)):
r, c = bomblist.popleft()
y, x, totm, tots, d = arr[r][c].pop()
# 질량이 0이 되면 소멸
if totm //5 == 0:
continue
if d != -1:
for p in range(4):
Q.append((r, c, totm//5, tots//visit[r][c], p * 2))
else:
for p in range(4):
Q.append((r, c, totm//5, tots//visit[r][c], p * 2 + 1))
cnt += 1
anw = 0
for i in range(len(Q)):
y, x, m, s, d = Q[i]
anw += m
print(anw)
Author And Source
이 문제에 관하여([BOJ]20056 마법사 상어와 파이어볼(Python) - 삼성SW역량테스트 기출), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@smkim104/BOJ20056-마법사-상어와-파이어볼Python-삼성SW역량테스트-기출저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)