[문제풀이-백준] 20056. 마법사 상어와 파이어볼

풀이

시뮬레이션

구현 방법

• 움직이기 전 파이어볼의 정보를 저장하는 before 리스트
  • 이동 로직 함수를 만들어서 이동
• visited를 딕셔너리로 만들어서 해당위치에 있는 파이어볼 갯수 파악
  • 딕셔너리 키에 튜플도 가능
• visited에 있는 데이터들을 before에 넣음
• 위 과정을 K번 반복

어려웠던 점

• 행이나 열 값이 -가 될 때의 점화식 만드는 과정이 어려웠음
  • s가 N보다 크거나 같을 경우 고려해야함
    • N이나 2N, 3N 등은 결국 속력이 같음
  • 현재 위치에서 s만큼 이동시켰을때 음수인지 아닌지에 따라 분기
    • 음수라면 ny = N - abs(이동시켰을 때의 값(음수))

코드

# 해당 위치에 파이어볼이 여러개 있을 경우 
def divide(tlst):
    nm = ns = 0
    isCheck = [0,0]
    for lst in tlst:
        y, x, m, s, d = lst
        nm += m
        ns += s
        isCheck[d % 2] = 1
    nm //= 5
    ns //= len(tlst)
    if isCheck == [1,1]:
        dlst = [1, 3, 5, 7]
    else:
        dlst = [0, 2, 4, 6]
    if nm != 0:
        for i in range(4):
            before.append([y,x,nm,ns,dlst[i]])

# 방향에 따라 이동 
def move(tlst):
    y, x, m, s, d = tlst
    ny,nx = y,x
    if d == 0:
        ns = s
        if s >= N: # N은 한바퀴 돌아서 제자리이므로 2N,3N과 같음 
            ns %= N
        ny = y - ns
        if ny < 0: # 음수라면 다시 뒤에서부터 순회해야하므로 
            ny = N - abs(ny)
    elif d == 1:
        ns = s
        if s >= N:
            ns %= N
        ny = y - ns
        if ny < 0:
            ny = N - abs(ny)
        nx = (x + s) % N
    elif d == 2:
        nx = (x + s) % N
    elif d == 3:
        ny = (y + s) % N
        nx = (x + s) % N
    elif d == 4:
        ny = (y + s) % N
    elif d == 5:
        ns = s
        if s >= N:
            ns %= N
        nx = x - ns
        if nx < 0:
            nx = N - abs(nx)
        ny = (y + s) % N
    elif d == 6:
        ns = s
        if s >= N:
            ns %= N
        nx = x - ns
        if nx < 0:
            nx = N - abs(nx)
    else:
        ns = s
        if s >= N:
            ns %= N
        ny = y - ns
        if ny < 0:
            ny = N - abs(ny)
        ns = s
        if s >= N:
            ns %= N
        nx = x - ns
        if nx < 0:
            nx = N - abs(nx)

    if (ny,nx) in visited:
        visited[(ny,nx)].append([ny,nx,m,s,d])
    else:
        visited[(ny,nx)] = [[ny,nx,m,s,d]]


N,M,K = map(int,input().split())
before = [] # 이동 전 파이어볼의 정보를 담은 리스트 
for _ in range(M):
    arr = list(map(int,input().split()))
    arr[0] -= 1
    arr[1] -= 1
    before.append(arr)
count = 0
while count < K:
    count += 1
    visited = dict() # 해당 위치에 파이어볼의 정보를 담는 딕셔너리 
    for lst in before:
        move(lst)
    before = []
    for p,plst in visited.items():
        if len(plst) > 1:
            divide(plst)
        else:
            before.append(plst[0])
answer = 0
for lst in before:
    answer += lst[2]
print(answer)