[알고리즘] 백준 21610 Python

 

분류

구현

혼자 힘으로 해결 했는가?

O

느낀 점

그냥 순수 구현 그 자체이다.

재미는 있었다.

 

구현 중 제일 짜증나는 형태는 배열을 돌리고 뒤집고.. 난리 치는 경우인데 이 문제는 깔끔했다.

 

다만 이동 계수 부분을 잘못 체크해서 조금 애먹었다.

---

 

내가 작성한 코드

from sys import stdin
from collections import deque

N,M = map(int, input().split())

graph = []

for i in range(N):
    graph.append(list(map(int, stdin.readline().rstrip().split())))

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

ddy = [-1,-1,1,1]
ddx = [-1,1,-1,1]

cloud = deque()
prev = deque()
move = deque()

init = True

for i in range(M):
    d,s = map(int, stdin.readline().rstrip().split())
    move.append((d,s))


round = 1
for i in range(M):

    # print("the round : %d" %(round))

    # for i in graph:
    #     print(*i)

    # 구름 만들기
    if init:
        cloud.append((N-2, 0))
        cloud.append((N-2, 1))
        cloud.append((N-1, 0))
        cloud.append((N-1, 1))
        init = False
    else:
        for i in range(N):
            for j in range(N):
                if graph[i][j] >= 2 and (i,j) not in prev:
                    graph[i][j] -= 2
                    cloud.append((i,j))
        prev.clear()

        # print ("the graph after make cloud")
        # for i in graph:
        #     print(*i)

    d, s = move.popleft()
    while cloud:
        # 구름 이동 시키기
        y,x = cloud.popleft()

        ny = y + s * dy[d]
        nx = x + s * dx[d]

        # 보정
        while ny < 0:
            ny += N
        while ny >= N:
            ny %= N
        while nx < 0:
            nx += N
        while nx >= N:
            nx %= N
        # 비 내리기

        graph[ny][nx] += 1

        # 구름 없애기
        prev.append((ny,nx))

    # print("the graph after rain")
    # for i in graph:
    #     print(*i)
    # 물 복사

    for yy,xx in prev:

        bug = 0
        for i in range(4):
            nyy = yy + ddy[i]
            nxx = xx + ddx[i]

            if 0 <= nyy < N and 0 <= nxx < N:
                if graph[nyy][nxx] > 0:
                    bug += 1
        graph[yy][xx] += bug
    round += 1

# 물 다 더하기

water = 0

for i in range(N):
    for j in range(N):
        if graph[i][j] >= 2 and (i, j) not in prev:
            graph[i][j] -= 2
            cloud.append((i, j))

# print()
# for i in graph:
#     print(*i)

for i in range(N):
    for j in range(N):
        water += graph[i][j]

print(water)

 

 

 

---

비슷한 문제들