[BOJ20056 - Python] 마법사 상어와 파이어볼

문제

---

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

 

마법사 상어는 N×N 격자(1번~N번)에 파이어볼 M개를 발사한다.

격자의 행과 열 각각은 1번과 N번이 연결되어 있다.

 

파이어볼은 각각 위치(r행 c열), 질랑 m, 방향 d, 속력 s의 정보를 가지며, 해당 위치에서 대기하고 있다.

 

마법사 상어가 모든 파이어볼에게 K번의 이동을 명령한다.

파이어볼은 자신의 방향으로 속력 s칸만큼 이동하는데, 방향은 다음의 8개 칸의 방향을 의미한다.

 

 

파이어볼이 한번 이동을 할 때마다 2개 이상의 파이어볼이 있는 칸에서 다음의 일들이 각각 일어난다.

1. 같은 칸에 있는 파이어볼이 모두 하나로 합쳐진다.

2. 파이어볼은 4개의 파이어볼로 나누어진다.

3. 나누어진 파이어볼의 질량 : ⌊(합쳐진 파이어볼 질량의 합)/5⌋

4. 나누어진 파이어볼의 속력 : ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋

5. 합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수인 경우 방향은 0, 2, 4, 6 / 그렇지 않으면 1, 3, 5, 7

6. 질량이 0인 파이어볼은 소멸되어 없어진다.

 

이동을 K번 명령한 후 남아있는 파이어볼 질량의 합을 구하는 것이 문제이다.

 

 

풀이

---

파이어볼이 이동을 한 후 한 격자에 여러 개의 파이어볼이 존재할 수 있다.

이에 빈 리스트([]) 하나를 가지는 N×N의 이차원 배열로 격자를 생성해주었다.

grid = [[[] for _ in range(N)] for _ in range(N)]  # 파이어볼 번호 리스트

초기 상태 (N=7)

 

파이어볼이 격자 어느 한 곳에 위치하게 된다면 그 파이어볼의 인덱스를 리스트에 넣어주면 된다.

 

파이어볼이 이동했을 때마다 격자를 출력한 결과 (예제 4번)

 

파이어볼은 fireball이라는 리스트에 저장된다. 격자에 저장되는 파이어볼 인덱스는 fireball 리스트 상의 인덱스이다.

입력을 받아와 초기화하는 부분은 다음과 같다.

fireball = []  # 위치(r, c), 질량 m, 속력 s, 방향 d
for _ in range(M):
    temp = list(map(int, sys.stdin.readline().split()))
    temp[0] -= 1
    temp[1] -= 1
    fireball.append(temp)

* 위치, 질량, 속력, 방향을 저장하는 순서 주의하기!

 

---

프로그램의 큰 틀은

     1. 파이어볼 이동

     2. 파이어볼 연산 (fireball 리스트 리셋)

이를 K번 반복하는 것이다.

for _ in range(K):
    move()  # 이동
    fireball = reset_fireball()  # 연산

 

먼저 move() 함수를 보자.

dy = (-1, -1, 0, 1, 1, 1, 0, -1)
dx = (0, 1, 1, 1, 0, -1, -1, -1)

def move():
    for i in range(len(fireball)):
        r, c, m, s, d = fireball[i]
        grid[(r + dy[d] * s) % N][(c + dx[d] * s) % N].append(i)

격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있다고 했을 때, 1번 행은 N번과 연결 & 1번 열은 N번 열과 연결되어 있다.

 

따라서 원래 (r, c)에 위치해있던 파이어볼이 방향 d로 속력 s칸 만큼 이동했다고 했을 때

파이어볼이 도착한 y좌표와 x좌표 각각은 (원래 위치 + 이동한 거리)%N을 통해 얻을 수 있다.

 

---

그 다음, 파이어볼 이동 후의 연산을 담당하는 reset_fireball() 함수를 보자.

이 함수에서는 새 리스트(new)를 반환하여 기존의 fireball 리스트에 덮어 씌워줄 것이다. (이동 후 파이어볼 목록을 갱신)

 

먼저 격자에 저장된 리스트들을 하나하나 본다.

 

현재 보고 있는 격자에 파이어볼이 존재한다면

그곳에 저장되어 있는 인덱스를 통해 fireball 리스트에서 파이어볼의 정보를 가져와 연산을 수행,

다음 이동에 참가하는 파이어볼들의 정보를 new 리스트에 전부 추가해주면 되는 것이다.

def reset_fireball():
    global grid
    new = []  # new fireball list

    for y in range(N):
        for x in range(N):
        
            ...

    return new

 

1. 파이어볼이 1개 존재하는 경우

해당 파이어볼의 위치 값들만 바꿔서 new에 추가한 후 해당 격자 부분을 빈 리스트로 초기화한다.

# 파이어볼 1개 존재하는 경우
if len(grid[y][x]) == 1:
    r, c, m, s, d = fireball[grid[y][x][0]]
    new.append([y, x, m, s, d])
   
 ...
 
 grid[y][x] = []  # 초기화

 

2. 파이어볼이 존재하지 않는 경우

아무 연산을 진행하지 않는다.

# 파이어볼 존재하지 않는 경우
elif len(grid[y][x]) == 0:
    continue

 

3. 파이어볼이 2개 이상 존재하는 경우

파이어볼의 질량과 속력은 합쳐지는 파이어볼의 질량과 속력을 모두 더하여 연산을 진행해주면 된다.

 

살짝 고민을 해야 했던 부분은 파이어볼의 방향을 정하는 부분이었다.

합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수인 경우 방향은 각각 0, 2, 4, 6이 되고, 그렇지 않다면 각각 1, 3, 5, 7이 된다는 조건이 있었다.

 

나는 아래의 세 변수들을 통해 이 부분을 구현해주었다.

d_list = [(0, 2, 4, 6), (1, 3, 5, 7)]  # 모두 짝수 또는 홀수 / 그 외
d_idx = 0  # d_list 인덱스
d_status = 0 if fireball[grid[y][x][0]][4] % 2 == 0 else 1  # 짝수일 경우 0 / 홀수일 경우 1

d_idx 변수에 0이 저장되어 있을 때는 합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수인 경우이며,

1이 저장되어 있을 때는 그렇지 않은 경우이다.

후에 d_list[d_idx]를 통해 나누어진 파이어볼 각각에 어떤 값을 저장해주어야 하는지 알아낼 수 있다.

 

d_status 변수에는 현재 보고 있는 격자에 저장되어 있는 파이어볼 중 첫번째 파이어볼의 방향이 짝수인지, 홀수인지의 상태를 저장해준다. (짝수일 경우 : 0 / 홀수일 경우 : 1) - 삼항 연산자로 한번에 처리 가능

 

현재 보고 있는 격자에 저장되어 있는 파이어볼들에 대하여 다음의 연산이 각각 진행된다.

for idx in grid[y][x]:
    d_temp = 0 if fireball[idx][4] % 2 == 0 else 1  # 짝수일 경우 0 / 홀수일 경우 1
    if d_temp != d_status:
        d_idx = 1

 

즉, 현재 보고 있는 파이어볼의 방향이 짝수인지, 홀수인지를 봐서

첫번째 파이어볼 방향의 짝수, 홀수 상태와 다르다면 d_idx를 1로 바꿔주는 아이디어이다.

 

함수의 전체 코드는 다음과 같다.

# 파이어볼 2개 이상 존재하는 경우
else:
    m, s = 0, 0  # 질량, 속력
    d_status = 0 if fireball[grid[y][x][0]][4] % 2 == 0 else 1  # 짝수일 경우 0 / 홀수일 경우 1
    d_idx = 0  # d_list 인덱스

    for idx in grid[y][x]:
        m += fireball[idx][2]
        s += fireball[idx][3]
        d_temp = 0 if fireball[idx][4] % 2 == 0 else 1  # 짝수일 경우 0 / 홀수일 경우 1
        if d_temp != d_status:
            d_idx = 1

    m //= 5  # ⌊(합쳐진 파이어볼 질량의 합)/5⌋
    if m == 0:  # 질량이 0인 파이어볼은 소멸
        grid[y][x] = []  # 초기화
        continue

    s //= len(grid[y][x])  # ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋

    for i in range(4):
        new.append([y, x, m, s, d_list[d_idx][i]])

grid[y][x] = []  # 초기화

 

파이어볼 2개 이상 존재하는 경우에서 가장 중요한 부분은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋하였을 때 0이 되었을 경우에 대한 처리이다!!!

이 부분을 정교하게 처리해주지 않아서 디버깅하는 데에 시간을 꽤 오래 썼다...

 

연산 후 해당 격자 부분을 빈 리스트로 꼭 초기화 해주어야 하는데,

나는 if-elif-else 문이 끝나고 초기화해주는 부분을 작성해주면 모든 경우에 대해서 잘 진행될 것이라고 생각했다.

 

하지만!!! continue를 작성하면 해당 부분은 실행되지 않는다!!!

m==0인 경우 continue 전에 초기화 코드를 작성해주니 런타임 에러(IndexError)가 해결되었다.

 

만약 계속 알 수 없는 에러가 난다면 질량이 0이 되어 소멸되는 부분을 잘 확인해보길 바란다.

 

 

코드

---

import sys

N, M, K = map(int, sys.stdin.readline().split())  # NxN 격자 / M개의 파이어볼

grid = [[[] for _ in range(N)] for _ in range(N)]  # 파이어볼 번호 리스트

fireball = []  # 위치(r, c), 질량 m, 속력 s, 방향 d
for _ in range(M):
    temp = list(map(int, sys.stdin.readline().split()))
    temp[0] -= 1
    temp[1] -= 1
    fireball.append(temp)

dy = (-1, -1, 0, 1, 1, 1, 0, -1)
dx = (0, 1, 1, 1, 0, -1, -1, -1)
d_list = [(0, 2, 4, 6), (1, 3, 5, 7)]  # 모두 짝수 또는 홀수 / 그 외


def move():
    for i in range(len(fireball)):
        r, c, m, s, d = fireball[i]
        grid[(r + dy[d] * s) % N][(c + dx[d] * s) % N].append(i)


def reset_fireball():
    global grid
    new = []  # new fireball list

    for y in range(N):
        for x in range(N):
            # 파이어볼 1개 존재하는 경우
            if len(grid[y][x]) == 1:
                r, c, m, s, d = fireball[grid[y][x][0]]
                new.append([y, x, m, s, d])

            # 파이어볼 존재하지 않는 경우
            elif len(grid[y][x]) == 0:
                continue

            # 파이어볼 2개 이상 존재하는 경우
            else:
                m, s = 0, 0  # 질량, 속력
                d_status = 0 if fireball[grid[y][x][0]][4] % 2 == 0 else 1  # 짝수일 경우 0 / 홀수일 경우 1
                d_idx = 0  # d_list 인덱스

                for idx in grid[y][x]:
                    m += fireball[idx][2]
                    s += fireball[idx][3]
                    d_temp = 0 if fireball[idx][4] % 2 == 0 else 1  # 짝수일 경우 0 / 홀수일 경우 1
                    if d_temp != d_status:
                        d_idx = 1

                m //= 5  # ⌊(합쳐진 파이어볼 질량의 합)/5⌋
                if m == 0:  # 질량이 0인 파이어볼은 소멸
                    grid[y][x] = []  # 초기화
                    continue

                s //= len(grid[y][x])  # ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋

                for i in range(4):
                    new.append([y, x, m, s, d_list[d_idx][i]])

            grid[y][x] = []  # 초기화

    return new


for _ in range(K):
    move()  # 이동
    fireball = reset_fireball()  # 연산

result = 0
for f in fireball:
    result += f[2]
print(result)

차근차근 꼼꼼히를 곁들인 인간이 되자.