[Python] n20056번 | 마법사 상어와 파이어볼

---

* 주어진 조건 *

격자 크기 : N X N

파이어볼 : M개

질량 : m

방향 : d

속력 : s

위치 : (r,c) r은 행, c는 열

파이어볼의 방향

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

=> 이 문구를 이해하는 데 꽤나 시간이 오래 걸렸..다.. 바보인가부다..

1번 행에서 격자 밖인 0번 행으로 넘어갈 경우에는 격자 밖을 벗어나는 게 아니라 N번 행으로 넘어간다는 뜻이다.

순환시스템이라고 보면 되려나..? ㅎ..ㅎ

 

* 과정 *

1. 모든 파이어볼이 자신의 방향 d로 속력 s칸 만큼 이동한다

2. 이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 존재하는 칸에서는 다음과 같은 일이 일어난다.

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

     2) 파이어볼은 다시 4개의 파이어볼로 나눠진다.

     3) 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다.

         1. 질량은 합쳐진 파이어볼 질량의 합/5

         2. 속력은 (합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)

         3. 합쳐지는 파이어볼의 방향이 모두 홀수, 또는 짝수이면 방향은 0,2,4,6이고 그렇지 않으면 1,3,5,7이다.

         4. 질량이 0인 파이어볼은 소멸되어 사라진다.

 

=> 마법사 상어가 이동을 k번 명령한 후, 남아있는 파이어볼 질량의 합을 구해보기!

 

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

 

---

1. 입력값 받아오기

N : 격자 크기, M : 파이어볼 개수, K: 이동횟수

M_list : 파이어볼의 정보

N, M, K = map(int, input().split())
M_list = [list(map(int, input().split())) for _ in range(M)]

---

2. Map 리스트 초기화하기

Map = [[[] for _ in range(N)] for _ in range(N)] 

 

 

-> 일단 맵 형식이니까 2차원 배열 이상이어야 하고,

파이어볼의 정보들을 리스트 형태로 저장했으니까,

이것들을 맵에 저장하려면

3차원 배열을 초기화해야 한다.

 

이 부분이 헷갈려서 애를 좀 먹었다..

그래서 나중에도 기억하기 쉽게 정리를 해보려 한다.

 

일단 Map1이라는 3차원 배열을 생성!

N은 4라고 가정한다.

Map1=[[[] for _ in range(N)] for _ in range(N)]
#[[], [], [], [], [], [], []]

print(Map1[0])
print(Map1[0][0])
Map1[0][0].append([1,2,3])
print(Map1[0][0])
print(Map1[0][0][0])
print(Map1[0][0][0][0])

'''
[]
[[1, 2, 3]]
[1, 2, 3]
1
'''

3차원 배열이면 [][][] 3개까지만 쓸 수 있다.

0을 쓰게 되면 append시 index=1부터 추가되니까 빈 배열로 초기화해야한다.

 

Map1[0][0] 즉 0행 0열에 [1,2,3]이라는 리스트 자체를 append 해주면,

3차원 배열에서 4차원 배열로 변경된다.

왜 리스트 형태로 넣어줘야 하냐면,

한 칸에 들어갈 수 있는 파이어볼의 개수가 여러개이기 때문에,

이를 구별하기 위해선 리스트 형태로 넣어줘야 한다.

 

 

Map1[0][0].append([1,2,3])

> Map1 = 4차원 배열 형태로 출력

> Map1[0] = [[[1,2,3]],[],[],[]], 3차원 배열 형태로 출력

> Map1[0][0] = [[1,2,3]], 2차원 배열 형태로 출력

> Map1[0][0][0] = [1,2,3] , 1차원 배열 형태로 출력

---

3. x좌표, y좌표 인덱스 맞추기

파이어볼의 x,y좌표는 각각 1부터 시작한다고 문제에서 가정했으므로,

맵 형식에 맞추기 위해 -1씩 계산해준다.

 

for i in range(M):
    M_list[i][0] -= 1  # x좌표 -1 감소
    M_list[i][1] -= 1  # y좌표 -1 감소
    Map[M_list[i][0]][M_list[i][1]].append([M_list[i][2], M_list[i][3], M_list[i][4]])  # Map리스트에 파이어볼 리스트 담아두기

맵에는 x,y은 내용 빼고 m, s,d의 정보만 넣는다.

append시 []리스트 형태로 넣어줘야 한다.

 

---

4. 모든 파이어볼 이동하기

일단, 파이어볼을 먼저 이동 시켜놓고나서

계산을 진행해야 한다.

그런데 이동횟수를 다 채우라는 게 아니라,

이동을 1번 할때마다 이동 해야하는 파이어볼들을 이동하고,

그 이동이 끝나면, 이제 조건을 살펴본다.

그리고 조건 살펴보기가 끝났으면 다시 이동을 하고, 이 과정이 반복된다.

(k 값에 따라 위 과정을 수행해야 하는 횟수가 달라진다)

 

temp라는 3차원 빈 배열을 생성한다.

Map의 내용이 바뀌면, 계산이 제대로 이루어지지 않기 때문에

temp로 계산하고, 마지막에 Map에 deepcopy 해주기!

 

# 0, 1, 2, 3, 4, ... 순으로
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]

for _ in range(K):  # K는 이동횟수
    temp = [[[] for _ in range(N)] for _ in range(N)]  # ***    
    for i in range(N):
        for j in range(N):
            if Map[i][j] != []:  # M은 파이어볼 개수
                for x in range(len(Map[i][j])):
                    m, s, d = Map[i][j][x]
                    nx = i + dx[d] * s
                    ny = j + dy[d] * s
                    nx = (nx + N) % N
                    ny = (ny + N) % N
                    temp[nx][ny].append([m, s, d])
                    
 	# 2. 2개 이상의 파이어들이 있는 칸을 찾아가서 4개의 파이어들로 다시 만드는 과정
    for x in range(N):
        for y in range(N):
            if len(temp[x][y]) > 1:
                list_cnt = len(temp[x][y])
                n_m, n_s, d = 0, 0, []
                for z in range(list_cnt):
                    n_m += temp[x][y][z][0]
                    n_s += temp[x][y][z][1]
                    d.append(temp[x][y][z][2] % 2)
                n_m = int(n_m // 5)
                n_s = int(n_s / list_cnt)
                temp[x][y] = []
                if n_m != 0:
                    if sum(d) == 0 or sum(d) == list_cnt:  # 모두 홀수이거나 또는 짝수인 경우
                        for i in range(4):
                            temp[x][y].append([n_m, n_s, i * 2])
                    else:
                        for i in range(4):
                            temp[x][y].append([n_m, n_s, i * 2 + 1])
    Map = deepcopy(temp)

만약 맵의 요소가 비어있지 않은 경우에만 이동을 수행하게끔 한다.

len(Map[i][j])는 어떤 역할을 하냐면,

칸에 담겨져 있는 파이어볼의 개수를 의미한다.

 

nx = i + dx[d] * s
ny = j + dy[d] * s

d 방향으로 s칸만큼 이동한 값을 nx,ny에 각각 대입한다.

nx = (nx + N) % N
ny = (ny + N) % N

> 격자 밖을 벗어나는 순간을 대비하기 위한 과정.

만약 행과 열의 값이 -1,-1로 넘어왔다면?

nx=(-1+4) % 4 = 3

ny=(-1+4) % 4 = 3

 

만약 행과 열의 값이 5,6이라면?

nx=(5+4) % 4 = 1

ny=(6+4) % 4 = 2

 

이동된 좌표로 파이어볼의 정보가 담긴 리스트를 넘겨준다.

이때 tmp 리스트를 사용한다.

 

---

5. 2개 이상의 파이어볼들이 있는 칸을 찾아가서 4개의 파이어볼로 다시 만드는 과정

# 2. 2개 이상의 파이어들이 있는 칸을 찾아가서 4개의 파이어들로 다시 만드는 과정
    for x in range(N):
        for y in range(N):
            if len(temp[x][y]) > 1:
                list_cnt = len(temp[x][y])
                n_m, n_s, d = 0, 0, []
                for z in range(list_cnt):
                    n_m += temp[x][y][z][0]
                    n_s += temp[x][y][z][1]
                    d.append(temp[x][y][z][2] % 2)
                n_m = int(n_m // 5)
                n_s = int(n_s / list_cnt)
                temp[x][y] = []
                if n_m != 0:
                    if sum(d) == 0 or sum(d) == list_cnt:  # 모두 홀수이거나 또는 짝수인 경우
                        for i in range(4):
                            temp[x][y].append([n_m, n_s, i * 2])
                    else:
                        for i in range(4):
                            temp[x][y].append([n_m, n_s, i * 2 + 1])
    Map = deepcopy(temp)

 

 

---

6. 남아있는 파이어볼 질량의 합을 구하는 과정

answer = 0
for i in range(N):
    for j in range(N):
        if Map[i][j]:  # 내용물이 있을 경우를 찾는다.
            len_num = len(Map[i][j])
            for n in range(len_num):
                answer += Map[i][j][n][0]
print(answer)