Easy is Perfect

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

  • melonicedlatte
  • Apr 17, 2021


1. 문제

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

2. 풀이

삼성 SW 역량테스트 문제입니다. 격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다라는 문장이 처음에는 좀 헷갈렸습니다. 좀 더 읽다보니 원형 큐와 같은 구조로 1과 N이 이어져있는 구조라는 것을 알게 되었습니다. 구현은 큰 문제 없이 잘 된 문제인 것 같습니다.

풀이 방법은 아래와 같습니다. 자세한 사항은 소스코드를 봐주세요.

  • 불들을 저장하는 list 를 생성하여 [r, c, m, s, d] 값을 저장합니다.
  • 불들을 이동 시킨 후에 동일한 위치에 있는 불들을 확인하기 위하여 dictionary를 사용했습니다.
N, M, K = map(int, input().split())
# r, c, m, s, d 순서
fire_list = []
# 0, 1, 2, 3, 4, 5, 6, 7
WAY_r = [-1, -1, 0, 1, 1, 1, 0, -1]
WAY_c = [0, 1, 1, 1, 0, -1, -1, -1]
for _ in range(M):
    r, c, m, s, d = map(int, input().split())
    fire_list.append([r-1,c-1,m,s,d])

def fireballs_move():
    global fire_list
    for f_i, fire in enumerate(fire_list):
        fire_list[f_i][:2] = [(fire[0]+WAY_r[fire[4]]*fire[3])%N, (fire[1]+WAY_c[fire[4]]*fire[3])%N]

def fireballs_splits():
    global fire_list
    # 모든 fireball 을 dict에 넣기
    dict = {}
    for f_i, fire in enumerate(fire_list):
        if dict.get(str(fire[:2]), False):
            dict[str(fire[:2])].append(f_i)
        else:
            dict[str(fire[:2])] = [f_i]

    # 이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다.
    for key in dict:
        if len(dict[key]) <= 1:
            continue
        # 같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다.
        now_r, now_c = fire_list[dict[key][0]][:2]
        n_fire_weight = fire_list[dict[key][0]][2]
        n_fire_speed = fire_list[dict[key][0]][3]
        n_fire_way = fire_list[dict[key][0]][4] % 2
        fire_list[dict[key][0]] = -1
        for f_i in dict[key][1:]:
            n_fire_weight += fire_list[f_i][2]
            n_fire_speed += fire_list[f_i][3]
            n_fire_way += fire_list[f_i][4] % 2
            fire_list[f_i] = -1

        # 파이어볼은 4개의 파이어볼로 나누어진다.
        # 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다.
        # 질량은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋이다.
        # 속력은 ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋이다.
        # 합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 된다.
        new_weight = n_fire_weight//5
        new_speed = n_fire_speed//len(dict[key])
        new_way = [0,2,4,6] if n_fire_way == 0 or n_fire_way == len(dict[key]) else [1,3,5,7]

        # 질량이 0인 파이어볼은 소멸되어 없어진다.
        if new_weight == 0:
            continue
        for n_fire in range(4):
            fire_list.append([now_r, now_c, new_weight, new_speed, new_way[n_fire]])

    # 불필요한 불은 제거
    fire_list = [fire for fire in fire_list if fire != -1]

for _ in range(K):
    fireballs_move()
    fireballs_splits()
print(sum([fire[2] for fire in fire_list]))



Search