백준 마법사 상어와 파이어볼[20056] 파이썬(Python) 코드 + 해설

백준 20056 마법사 상어와 파이어볼

 

1.  문제 해설

마법사 상어는 크기가N×N인 격자에 파이어볼 M개를 발사한다. 각 파이어볼은 위치 (ri,ci), 질량 mi​, 속력 si, 방향 di를 가진다.

격자는 행과 열이 1부터 N까지 번호가 매겨져 있으며, 1번 행은 N번 행과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다. 즉, 격자는 토로이드 형태로 연결되어 있다.

마법사 상어는 파이어볼에게 K번 이동을 명령하며, 각 이동마다 다음이 일어난다:

1. 모든 파이어볼이 자신의 방향 did_idi​로 속력 sis_isi​만큼 이동한다. 이동 중에는 같은 칸에 여러 파이어볼이 있을 수 있다.
2. 이동이 끝난 후, 2개 이상의 파이어볼이 있는 칸에서는 다음이 일어난다:
   • 같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다.
   • 파이어볼은 4개의 파이어볼로 나누어진다.
   • 나누어진 파이어볼의 질량은 ⌊ 합쳐진 질량의 합 / 5 ⌋이다.
   • 나누어진 파이어볼의 속력은 ⌊ 합쳐진 속력의 합 / 합쳐진 파이어볼의 개수 ⌋ 이다.
   • 합쳐진 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 새로운 파이어볼의 방향은 [0, 2, 4, 6]이고, 그렇지 않으면 [1, 3, 5, 7]이다.
   • 질량이 0인 파이어볼은 소멸한다.

K번 이동 후 남아있는 파이어볼의 질량의 합을 구하는 것이 목표이다.

2.  문제 해결 방법

1. 자료 구조 설계
   • 파이어볼의 정보를 저장하기 위해 리스트를 사용한다. 각 파이어볼은 위치 (r,c), 질량 m, 속력 s, 방향 d를 가진다.
   • 격자의 각 칸에 있는 파이어볼들을 저장하기 위해 2차원 리스트를 사용한다.
2. 시뮬레이션 구현
   • K번의 이동을 시뮬레이션한다.
   • 각 이동마다 다음을 수행한다:
     1. 파이어볼 이동
        • 모든 파이어볼을 현재 위치에서 방향 d로 속력 s만큼 이동시킨다.
        • 이동 중에 격자를 넘어가면 토로이드 형태로 연결되므로, 위치를 N으로 나눈 나머지를 이용하여 조정한다.
        • 이동 후의 파이어볼들을 새로운 격자에 저장한다.
     2. 파이어볼 합치기 및 분할
        • 이동이 모두 끝난 후, 각 칸에 있는 파이어볼들을 확인한다.
        • 두 개 이상의 파이어볼이 있는 칸에 대해 다음을 수행한다:
          • 파이어볼들을 합쳐 하나로 만든다.
          • 새로운 질량 m_new ​ =⌊ 5 / 총 질량 ​ ⌋
          • 새로운 속력 s_new ​ =⌊ 파이어볼 수 / 총 속력 ​ ⌋
          • 새로운 방향은 파이어볼들의 방향이 모두 홀수이거나 모두 짝수이면 [0, 2, 4, 6], 그렇지 않으면 [1, 3, 5, 7]
          • 질량이 0이면 해당 파이어볼은 소멸한다.
3. 파이어볼의 정보 관리
   • 이동 후의 파이어볼 리스트를 업데이트한다.
   • 새로운 파이어볼 리스트로 기존 리스트를 대체한다.

3.  구현 세부사항

1. 방향 벡터 설정
   • 방향에 따른 행과 열의 변화를 나타내는 리스트를 설정한다.
   • 방향 d에 따른 dr​=[−1,−1,0,1,1,1,0,−1], dc​=[0,1,1,1,0,−1,−1,−1]​​
2. 위치 계산
   • 새로운 위치는 (r+dr[d]×s)mod𝑁(c+dc[d]×s)modN 계산한다.
   • Python에서 인덱스는 0부터 시작하므로, 위치를 계산할 때 (r−1)과 (c−1)로 조정하고, 마지막에 위치를 0부터 N−1 사이로 맞춘다.
3. 격자 업데이트
   • 이동 후의 파이어볼들을 저장하기 위한 새로운 격자를 생성한다.
   • 각 위치에 파이어볼 정보를 추가한다.
4. 합치기 및 분할 처리
   • 각 칸에서 파이어볼이 2개 이상인 경우 합치기와 분할을 처리한다.
   • 새로운 파이어볼을 생성하여 격자에 추가한다.

4.  백준 20056 마법사 상어와 파이어볼 정답 파이썬 코드

N, M, K = map(int, input().split())
fireballs = []

for _ in range(M):
    r, c, m, s, d = map(int, input().split())
    fireballs.append([r - 1, c - 1, m, s, d])

# 방향 벡터
dr = [-1, -1, 0, 1, 1, 1, 0, -1]
dc = [0, 1, 1, 1, 0, -1, -1, -1]

for _ in range(K):
    grid = [[[] for _ in range(N)] for _ in range(N)]
    
    # 파이어볼 이동
    for fb in fireballs:
        r, c, m, s, d = fb
        nr = (r + dr[d] * s) % N
        nc = (c + dc[d] * s) % N
        grid[nr][nc].append([m, s, d])
    
    new_fireballs = []
    
    # 파이어볼 합치기 및 분할
    for r in range(N):
        for c in range(N):
            if len(grid[r][c]) == 0:
                continue
            if len(grid[r][c]) == 1:
                m, s, d = grid[r][c][0]
                new_fireballs.append([r, c, m, s, d])
            else:
                m_sum = sum(fb[0] for fb in grid[r][c])
                s_sum = sum(fb[1] for fb in grid[r][c])
                cnt = len(grid[r][c])
                m_new = m_sum // 5
                if m_new == 0:
                    continue
                s_new = s_sum // cnt
                dirs = [fb[2] % 2 for fb in grid[r][c]]
                if all(d == dirs[0] for d in dirs):
                    new_dirs = [0, 2, 4, 6]
                else:
                    new_dirs = [1, 3, 5, 7]
                for d in new_dirs:
                    new_fireballs.append([r, c, m_new, s_new, d])
    fireballs = new_fireballs

# 남아있는 파이어볼 질량의 합 계산
result = sum(fb[2] for fb in fireballs)
print(result)

 

도움이 되셨다면 공감과 댓글 부탁드립니다