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

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

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

 

 

 

실수한 목록 

1. 문제를 제대로 이해하지 않고, 넘어감

'1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.' 라는 말은 2차원 배열의 격자를 벗어나더라도 연결되어 있음을 의미한다.

 

ex)

3 x 3크기의 2차원 0-indexed 배열에서 (0,0)에서부터 열을 기준으로 +1 칸씩 이동해보자. 

 

1칸 이동 (0,0) -> 1칸 이동 (0,1) -> 1칸 이동 (0,2) 

 

여기서 한 칸을 더 이동하게 되면 (0,3)으로 벗어나게 된다. 하지만, 문제의 조건에 따라 움직일 경우 (0,3)이 아닌 (0,0)으로 가게 된다. 헷갈린다면 반대로 이동해보자.

 

(0,0)에서 열을 기준으로 -1칸을 움직이게 된다면 어떻게 될까. (0,-1)로 격자를 벗어나는 것이 아닌 (0,2)로 넘어간다. 다시 말해서, (0,0)과 (0,2)는 연결되어 있음을 의미한다.

(2차원 평면에 나타낸 세계 지도를 보면, 지도의 끝자락에서 더 가면 길이 없지만 3차원으로 표현된 지구본을 보면 지구는 둥글게 연결되어 있다 !)

 

 

.. (0,2)  (0,0) (0,1) (0,2)  (0,0) ..

.. (1,2)  (1,0) (1,1) (1,2)  (1,0) ..

.. (2,2)  (2,0) (2,1) (2,2)  (2,0) ..

 

2. 적절한 자료구조를 선정하는 데 긴 시간이 걸림

입력받은 파이어볼을 어떻게 관리해야할 지 오랜 시간을 고민했다. queue에 넣어서 관리할까? hashmap으로 좌표값을 key, 다른 정보들을 value로 저장할까? .. 삼성 기출 문제들을 많이 풀어보면서 유형을 익혀야겠다. 

 

 

 

 

오답 노트

1시간 30분동안 고민하고 문제를 해결했다. 난이도가 높지 않은 편이었음에도 불구하고, 시간을 많이 잡아먹었다. 중요한 핵심 포인트는 3가지로 정리할 수 있었다.

 

1. 격자를 벗어날 때 처리해주는 조건

nx = (x + speed * dx[direction]) % N
ny = (y + speed * dy[direction]) % N

 

2. 입력받은 파이어볼을 queue에 저장하고, move() 를 수행. 이동한 위치(board[nx][ny])에 질량, 속도, 방향 정보를 저장

 

3. board를 탐색하면서 파이어볼이 2개 이상 존재한다면, merge -> divide 작업을 수행

 

4. k의 반복 횟수에 따라 2-3 작업을 반복 

 

 

 

다른 접근 방법

여러 사람들의 풀이를 보면서 hashmap을 사용한 풀이도 발견했다. 하지만, 효율적인 풀이는 아니라고 생각이 들었다. 

 

 

 

python 풀이

import sys
from collections import deque

def move() :
    while fireballs :
        x, y, weight, speed, direction = fireballs.popleft()
        nx = (x + speed * dx[direction]) % N
        ny = (y + speed * dy[direction]) % N
        board[nx][ny].append([weight, speed, direction])

def merge_and_divide(i, j) :
    sum_weight, sum_speed, sum_odd, sum_even = 0, 0, 0, 0
    board_cnt = len(board[i][j])
    while board[i][j] :
        mm, ss, dd = board[i][j].pop(0)
        sum_weight += mm
        sum_speed += ss
        if dd % 2 == 1 :
            sum_odd += 1
        else :
            sum_even += 1

    nd = [1,3,5,7]
    if sum_odd == board_cnt or sum_even == board_cnt :
        nd = [0,2,4,6]

    if (sum_weight // 5) >= 1 :
        for d in nd :
            fireballs.append([i,j,sum_weight//5, sum_speed//board_cnt, d])


def check() :
    for i in range(N) :
        for j in range(N) :
            if len(board[i][j]) > 1 :
                merge_and_divide(i,j)

            if len(board[i][j]) == 1 :
                fireballs.append([i,j]+board[i][j].pop())


si = sys.stdin.readline
N,M,K=map(int,si().split())
fireballs = deque([])
board=[[[] for _ in range(N)]  for _ in range(N)]
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]

for _ in range(M) :
    row,col,_m,_s,_d = map(int,si().split())
    fireballs.append([row-1,col-1, _m, _s, _d])

for _ in range(K) :
    # 1.
    move()
    # 2.
    check()

print(sum([ val[2] for val in fireballs ]))