코딩하는 덕구 🐶

139. [삼성기출35]Python 백준 20056 마법사 상어와 파이어볼 본문

알고리즘 문제 풀이

139. [삼성기출35]Python 백준 20056 마법사 상어와 파이어볼

코딩하는 덕구 🐶 2023. 8. 14. 16:07
728x90

안녕하세요 코딩하는 덕구입니다.

파이썬 백준 20056 마법사 상어와 파이어볼 입니다.

https://www.acmicpc.net/problem/20056

 

20056번: 마법사 상어와 파이어볼

첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치

www.acmicpc.net

 

문제 접근

불을 k번 이동하고, 분화합니다.

여기서 분화는 이동이 아니고 그 자리에서 나눠지기만 합니다.

1. 불의 정보를 담는 큐 fire를 만들어 모두 pop하여 board에 표시합니다.

2. 2차원 리스트 board 전체를 순차탐색한 후

      - 길이가 2 이상이면 (불이 두개 이상) board[i][j]를 모두 pop하여 새로운 불을 만들고 조건에 따라 나눈후 fire에 넣습니다.

      - 1이면 그대로 fire에 넣습니다.

 

Python 정답 코드

백준 20056 마법사 상어와 파이어볼 파이썬 코드입니다. 설명은 아래에 있습니다.

from collections import deque
N, M, K = map(int, input().split())
fire = deque()
board = [[deque() for _ in range(N)] for _ in range(N)]
dr = [-1, -1, 0, 1, 1, 1, 0, -1]
dc = [0, 1, 1, 1, 0, -1, -1, -1]
for _ in range(M):
    fire.append(list(map(int, input().split())))

for k in range(K):
    #이동
    while fire:
        r, c, m, s, d = fire.popleft()
        nr, nc = (dr[d]*s + r + N) % N, (dc[d]*s + c + N) % N
        board[nr][nc].append([m, s, d])

    #분화
    for i in range(N):
        for j in range(N):
            if len(board[i][j]) >= 2:
                nm, ns, odd, even, length = 0, 0, 0, 0, len(board[i][j])
                while board[i][j]:
                    m, s, d = board[i][j].popleft()
                    nm += m
                    ns += s
                    if d % 2 == 0:
                        even += 1
                    else:
                        odd += 1

                if even == 0 or odd == 0:
                    nd = [0, 2, 4, 6]
                else:
                    nd = [1, 3, 5, 7]

                if nm//5 != 0:
                    for d in nd:
                        fire.append([i, j, nm//5, ns//length, d])

            elif len(board[i][j]) == 1:
                m, s, d = board[i][j].popleft()
                fire.append([i, j, m, s, d])

#남은질량 더하기
ans = 0
while fire:
    _, _, m, _, _ = fire.popleft()
    ans += m
print(ans)

 

Python 코드 설명

문제에서 주어진 변수들을 입력받아 저장합니다.

from collections import deque
N, M, K = map(int, input().split())
fire = deque()
board = [[deque() for _ in range(N)] for _ in range(N)]
dr = [-1, -1, 0, 1, 1, 1, 0, -1]
dc = [0, 1, 1, 1, 0, -1, -1, -1]
for _ in range(M):
    fire.append(list(map(int, input().split())))

 

 k번 반복하며

for k in range(K):

 

불들을 이동시킵니다. 

#이동
while fire:
    r, c, m, s, d = fire.popleft()
    nr, nc = (dr[d]*s + r + N) % N, (dc[d]*s + c + N) % N
    board[nr][nc].append([m, s, d])

 

 이동이 끝난 후 같은 곳에 불이 2개 이상있다면 분화해서 fire에 넣고, 아니라면 그냥 fire에 넣어줍니다.

#분화
for i in range(N):
    for j in range(N):
        if len(board[i][j]) >= 2:
            nm, ns, odd, even, length = 0, 0, 0, 0, len(board[i][j])
            while board[i][j]:
                m, s, d = board[i][j].popleft()
                nm += m
                ns += s
                if d % 2 == 0:
                    even += 1
                else:
                    odd += 1

            if even == 0 or odd == 0:
                nd = [0, 2, 4, 6]
            else:
                nd = [1, 3, 5, 7]

            if nm//5 != 0:
                for d in nd:
                    fire.append([i, j, nm//5, ns//length, d])

        elif len(board[i][j]) == 1:
            m, s, d = board[i][j].popleft()
            fire.append([i, j, m, s, d])

 

k번 반복이 끝나면 질량을 더해서 출력합니다.

#남은질량 더하기
ans = 0
while fire:
    _, _, m, _, _ = fire.popleft()
    ans += m
print(ans)

 

백준 20056 마법사 상어와 파이어볼 Python 코드였습니다.

감사합니다.

728x90