[백준] 21610번 마법사 상어와 비바라기

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

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

---

1. 접근 방식

• 문제를 읽으면서 필요한 함수를 미리 주석으로 기록해놓자

구현 문제이다. 지문이 길기 때문에 문제를 읽으면서 이전 내용이 휘발될 수 있다. 따라서 먼저 주석으로 어떤 역할을 하는 함수가 필요한지 작성해 놓았다. 나중에 문제를 풀 때 길을 잃지 않는 데 도움이 됐다.

또한 지문을 읽으며 필요한 함수들을 미리 정의했기 때문에 이후 구현은 간단하다. 문제를 이해하는 게 관건인 문제 같았다.

 

 

• 물의 양이 2 이상인 칸을 찾을 때를 주의하자

바로 직전에 구름이 있었던 칸은 제외해야 하는데, 그 방식에 따라 시간 초과가 발생할 수 있다.

처음에는 이전에 구름이 있던 칸을 리스트 except_clouds 저장해 둔 채, 어떤 위치 (i, j)가 except_clouds에 포함되는지 아닌지를 not in 연산으로 확인했다. 그러나 not in 연산은 일단 except_clouds 리스트를 모두 순회하기 때문에 시간 복잡도가 O(n)이라서 시간 초과가 났다.

따라서 O(1) 시간 복잡도로 (i, j)가 이전 구름이 있던 칸인지 확인하기 위해 visited 2차원 리스트를 사용하도록 하자.

 

 

 

2. 정답 코드

import sys

input = sys.stdin.readline

# 전체를 순회하며 물의 양이 2 이상인 칸 찾는 함수 (구름 있던 칸 제외) & -2하기
def find_where_clouds_will_be_created(visited):
    clouds = []

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

    return clouds

# 구름 이동 함수 & 물의 양 + 1
def move_clouds(clouds, d, s):
    dx = directions[d][0] * s
    dy = directions[d][1] * s

    moved_clouds = []
    for cloud in clouds:
        x = (cloud[0] + dx) % n
        y = (cloud[1] + dy) % n
        baskets[x][y] += 1
        moved_clouds.append((x, y))

    return moved_clouds

# 대각선 확인하고 물 양 증가하는 함수
def check_diagonal_and_add(clouds):
    diagonal = [(-1, -1), (-1, 1), (1, -1), (1, 1)]
    visited = [[False] * n for _ in range(n)]
    for cloud in clouds:
        x, y = cloud
        count = 0
        for d in diagonal:
            dx = x + d[0]
            dy = y + d[1]
            if -1 < dx < n and -1 < dy < n and baskets[dx][dy] > 0:
                count += 1

        baskets[x][y] += count
        visited[x][y] = True
    return visited


# main
n, m = map(int, input().split())
baskets = [list(map(int, input().split())) for _ in range(n)]
directions = [(), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1)]

# solution
result = [(n - 1, 0), (n - 1, 1), (n - 2, 0), (n - 2, 1)]
for _ in range(m):
    direction, speed = map(int, input().split())
    result = move_clouds(result, direction, speed)
    visited = check_diagonal_and_add(result)
    result = find_where_clouds_will_be_created(visited)
print(sum([sum(b) for b in baskets]))