[백준] 20056번 (python 파이썬)

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

 

구현문제이다.

 

명령에 대해서 그대로 따라서 구현하면 금방 구현할 수 있을것이다. ( 난 엄청 오래걸렸다.. )

1번 명령에서 중요한것이 파이어볼을 이동하는 것이다. 이동하는 좌표를 구하고 큐에 넣어서 마지막에 큐에서 빼면서 좌표에 대한 계산을 다 해줬다.

 

2번 명령은 만약에 계산된 좌표에 파이어볼이 2개 이상일때이다.

이때 중요한 것은 모두 홀수이거나 모두 짝수 일때 어떻게 계산하는 것이냐 이다.

처음에 생각한 방법은 모든 방향을 더했을때 짝수이면 모두 홀수 or 모두 짝수 라고 생각했다. ( 너무 안일했다..)

나중에 보니까 0, 1, 2, 3일때도 더하면 짝수가 나온다..

그래서 다시 생각한 방법은

2개 부터 방향 %2 를 한뒤 더한값이 합쳐진 파이어볼의 개수랑 같거나 0일때로 수정하였다.

ex)

0 1 2 3 이 한좌표에서 합쳐지면

0 % 2 = 0

1 % 2 = 1

2 % 2 = 0

3 % 2 = 1

0 + 1 + 0 + 1 = 2

합쳐진 파이어볼 개수 4 != 2 -> 모두 짝수 or 모두 홀수 가 아니다.

 

0 2 4 6

0 % 2 = 0

2 % 2 = 0

4 % 2 = 0

6 % 2 = 0

0 + 0 + 0 + 0 = 0 -> 모두 짝수

 

1 3 5 7

1 % 2 = 1

3 % 2 = 1

5 % 2 = 1

7 % 2 = 1

1 + 1 + 1 + 1 = 4 

합쳐진 파이어볼 개수 4 == 4 ->모두 홀수

 

이런식으로 구하였다.

    while queue:
        x, y, m, s, d = queue.popleft()
        cnt = 1
        if graph[x][y] == 0:
            graph[x][y] = [m, s, d, cnt]
        else:
            graph[x][y][0] += m
            graph[x][y][1] += s
            graph[x][y][3] += 1
            if graph[x][y][3] == 2: # <--이부분
                graph[x][y][2] %= 2
                graph[x][y][2] += (d % 2)
            else:
                graph[x][y][2] += (d % 2)

 

 

 

풀이 코드

from collections import deque

n, m, k = map(int, input().split(' '))
graph = [[0] * n for _ in range(n)]

dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]

for i in range(m):
    r, c, m, s, d = map(int, input().split(' '))  # x, y, 질량, 속력, 방향
    graph[r - 1][c - 1] = [m, s, d, 1]  


def solve():
    queue = deque()
    for i in range(n):
        for j in range(n):
            if graph[i][j] != 0:
                m = graph[i][j][0]
                s = graph[i][j][1]
                d = graph[i][j][2]
                if graph[i][j][3] == 1:
                    nx, ny = i + dx[d] * s, j + dy[d] * s
                    nx, ny = position(nx, ny)
                    queue.append([nx, ny, m, s, d])
                else:
                    start = 0
                    if not graph[i][j][2]:
                        start = 1
                    for k in range(start, 8, 2):
                        nx, ny = i + dx[k] * s, j + dy[k] * s
                        nx, ny = position(nx, ny)
                        queue.append([nx, ny, m, s, k])

            graph[i][j] = 0

    while queue:
        x, y, m, s, d = queue.popleft()
        cnt = 1
        if graph[x][y] == 0:
            graph[x][y] = [m, s, d, cnt]
        else:
            graph[x][y][0] += m
            graph[x][y][1] += s
            graph[x][y][3] += 1
            if graph[x][y][3] == 2:
                graph[x][y][2] %= 2
                graph[x][y][2] += (d % 2)
            else:
                graph[x][y][2] += (d % 2)



def position(nx, ny):
    abs_x = abs(nx) % n
    abs_y = abs(ny) % n
    if nx < 0:
        while nx < 0:
            nx += n
        abs_x = nx
    if ny < 0:
        while ny < 0:
            ny += n
        abs_y = ny
    return abs_x, abs_y


for _ in range(k):
    solve()
    for i in range(n):
        for j in range(n):
            if graph[i][j] != 0 and graph[i][j][3] > 1:
                m = graph[i][j][0] // 5
                if m == 0:
                    graph[i][j] = m
                    continue
                graph[i][j][0] = m
                s = graph[i][j][1] // graph[i][j][3]
                graph[i][j][1] = s
                if graph[i][j][2] == 0 or graph[i][j][2] == graph[i][j][3]:
                    graph[i][j][2] = True
                else:
                    graph[i][j][2] = False

answer = 0
for i in range(n):
    for j in range(n):
        if graph[i][j] != 0:
            if graph[i][j][3] > 1:
                answer += (graph[i][j][0] * 4)
            else:
                answer += graph[i][j][0]

print(answer)

20056