반응형
https://www.acmicpc.net/problem/20056
20056번: 마법사 상어와 파이어볼
첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치
www.acmicpc.net
import collections
import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())
table = [[collections.deque() for _ in range(n)] for _ in range(n)]
answer = 0
for i in range(m):
r, c, m, s, d = map(int, input().split())
table[r-1][c-1].append([m, s, d])
answer += m
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]
for _ in range(k):
move = [[collections.deque() for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
if len(table[i][j]) >= 1: # there are fireballs
while table[i][j]:
m, s, d = table[i][j].popleft()
x = i
y = j
# new position
nx = x + dx[d] * s
ny = y + dy[d] * s
if nx < 0:
while nx<0 or nx>=n:
nx += n
if nx >= n:
while nx<0 or nx>=n:
nx -= n
if ny < 0:
while ny<0 or ny>=n:
ny += n
if ny >= n:
while ny<0 or ny>=n:
ny -= n
# move
move[nx][ny].append([m, s, d])
for i in range(n):
for j in range(n):
if len(move[i][j]) == 1:
m, s, d = move[i][j].popleft()
table[i][j].append([m, s, d])
if len(move[i][j]) >= 2: # there are two or more
num = len(move[i][j])
nm, ns, nd = 0, 0, []
odd, even = 0, 0
while move[i][j]:
m, s, d = move[i][j].popleft()
nm += m
ns += s
if d%2 == 1:
odd += 1
else:
even += 1
answer -= m
nm = nm//5
ns = ns//num
if odd == 0 or even == 0: # all dir is same
nd = [0, 2, 4, 6]
else:
nd = [1, 3, 5, 7]
if nm != 0:
for w in range(4):
table[i][j].append([nm, ns, nd[w]])
answer += nm
print(answer)삼성기출.. 까다롭다
<배운 점>
1. 3차원 배열을 처음에
table = [[[]]*n for _ in range(n)]위와 같이 구성했었는데 이렇게 table을 초기화하니
append를 할때 해당 행 속 열 전체에 append가 되는 현상이 계속 발생했다.
이유는.. 정확히 모르겠다 아직도.. 그냥 안쓰는게 최선이다.
앞으로 다차원 배열 초기화는 아래와 같이 리스트 컴프리헨션 구문을 이용하는 것이 훨씬 좋을 것 같다.
table = [[collections.deque() for _ in range(n)] for _ in range(n)]
2. 맵을 순환할 때 인덱스 문제
인덱스 오류를 막기위해 아래처럼 약간의 뻘짓을 해주었는데 정말 비효율적인 짓이다.
if nx < 0:
while nx<0 or nx>=n:
nx += n
if nx >= n:
while nx<0 or nx>=n:
nx -= n
if ny < 0:
while ny<0 or ny>=n:
ny += n
if ny >= n:
while ny<0 or ny>=n:
ny -= n모듈러 연산을 활용하면 쉽게 처리가 가능하다.
이게 음수 인덱스에도 통한다는 사실은 처음 알았다.
nx = nx % n
ny = ny % n
<개선 코드>
import collections
import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())
table = [[collections.deque() for _ in range(n)] for _ in range(n)]
answer = 0
for i in range(m):
r, c, m, s, d = map(int, input().split())
table[r-1][c-1].append([m, s, d])
answer += m
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]
for _ in range(k):
move = [[collections.deque() for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
if len(table[i][j]) >= 1: # there are fireballs
while table[i][j]:
m, s, d = table[i][j].popleft()
# new position
nx = (i + dx[d] * s) % n
ny = (j + dy[d] * s) % n
# move
move[nx][ny].append([m, s, d])
for i in range(n):
for j in range(n):
if len(move[i][j]) == 1:
m, s, d = move[i][j].popleft()
table[i][j].append([m, s, d])
if len(move[i][j]) >= 2: # there are two or more
num = len(move[i][j])
nm, ns, nd = 0, 0, []
odd, even = 0, 0
while move[i][j]:
m, s, d = move[i][j].popleft()
nm += m
ns += s
if d%2 == 1:
odd += 1
else:
even += 1
answer -= m
nm = nm//5
ns = ns//num
if odd == 0 or even == 0: # all dir is same
nd = [0, 2, 4, 6]
else:
nd = [1, 3, 5, 7]
if nm != 0:
for w in range(4):
table[i][j].append([nm, ns, nd[w]])
answer += nm
print(answer)
댓글