백준21610) 마법사 상어와 비바라기 (lv.골드5)

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

21610번: 마법사 상어와 비바라기

 

 

시뮬레이션 및 구현 유형의 문제이다. 문제의 단계는 다음과 같다. 

1. 이동방향은 (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1)이다. 
2. n*n 만큼의 board와 , m 번의 이동방향 및 이동 카운트가 주어진다. 
3. 처음 구름의 위치는 (n-2, 0), (n-2, 1), (n-1, 0), (n-1, 1)이다. 
4. 구름이 주어진 방향으로 주어진 cnt 수만큼 이동한다. 
5. 이동한 구름안의 칸은 1만큼 물이 증가한다. (board[x][y] += 1)
6. 구름의 각칸마다 네 방향 대각선 쪽의 칸의 물양이 1 이상인 칸의 갯수를 구름의 각칸에 더한다. 
7. 전체 칸중에서 방금 구름이 아니었던 칸중에서 물 양이 2 이상인 칸은 다름 구름의 대상이 된다. 
8. 위의 과정을 m번만큼 반복한다. 
9. 결과적으로 board의 각 물의 양을 합한 값을 출력한다. 

 

 

처음 코드는 다음과 같이 짰고, pypy의 테스트가 통과하였다. 

import sys 
from collections import deque
n, m  = map(int, sys.stdin.readline().split())
board = []
directions = [(0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1)]

for _ in range(n) :
    board.append(list(map(int, sys.stdin.readline().split())))

def move(x, y, direction, cnt) :
    nx = (x + directions[direction][0]*(cnt%n) + n) % n 
    ny = (y + directions[direction][1]*(cnt%n) + n) % n
    return nx, ny

def count_diagonal_water(x, y) :
    for i in [1, 3, 5, 7] :
        nx = x + directions[i][0]
        ny = y + directions[i][1]
        if nx<0 or ny<0 or nx>=n or ny>=n or board[nx][ny]<1:
            continue
        board[x][y] += 1

q = deque()
q.extend([(n-2, 0), (n-2, 1), (n-1, 0), (n-1, 1)])

for _ in range(m) :
    direction, cnt = map(int, sys.stdin.readline().split())
    l = len(q)
    for _ in range(l) :
        x, y = q.popleft()
        q.append((move(x, y, direction-1, cnt)))
    nq = []

    while q : 
        x, y = q.popleft()
        board[x][y] += 1
        nq.append((x, y))

    for x, y in nq : 
        count_diagonal_water(x, y)

    for i in range(n):
        for j in range(n) :
            if not (i,j) in nq and board[i][j] >=2:
                q.append((i, j))
                board[i][j] -= 2

answer = 0 
for b in board : 
    answer += sum(b)
print(answer)

 

 

 

하지만 위의 코드는 python3에서 시간초과가 발생했는데 이는 not (i, j) in nq부분에서 nq 배열을 모두 돌면서 조회하기 때문이었다.  이를 해결하기 위해 visited 2차원 배열을 만들고 이를 이용해서 조회하도록 하였다. 

import sys 
from collections import deque
n, m  = map(int, sys.stdin.readline().split())
board = []
directions = [(0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1)]

for _ in range(n) :
    board.append(list(map(int, sys.stdin.readline().split())))

def move(x, y, direction, cnt) :
    nx = (x + directions[direction][0]*(cnt%n) + n) % n 
    ny = (y + directions[direction][1]*(cnt%n) + n) % n
    return nx, ny

def count_diagonal_water(x, y) :
    for i in [1, 3, 5, 7] :
        nx = x + directions[i][0]
        ny = y + directions[i][1]
        if nx<0 or ny<0 or nx>=n or ny>=n or board[nx][ny]<1:
            continue
        board[x][y] += 1

q = deque()
q.extend([(n-2, 0), (n-2, 1), (n-1, 0), (n-1, 1)])

for _ in range(m) :
    visited=[[False]*n for _ in range(n)]
    direction, cnt = map(int, sys.stdin.readline().split())
    l = len(q)
    for _ in range(l) :
        x, y = q.popleft()
        q.append((move(x, y, direction-1, cnt)))
    nq = []

    while q : 
        x, y = q.popleft()
        board[x][y] += 1
        nq.append((x, y))
        visited[x][y] = True

    for x, y in nq : 
        count_diagonal_water(x, y)

    for i in range(n):
        for j in range(n) :
            if not visited[i][j] and board[i][j] >=2:
                q.append((i, j))
                board[i][j] -= 2

answer = 0 
for b in board : 
    answer += sum(b)
print(answer)