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

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

아이디어

• N의 값이 그렇게 크지 않아서 반복문을 많이 써도 괜찮을 것 같다.
• 구름의 좌표가 리스트 인덱스 표기보다 1 커서 -1을 미리 해주고 사용하면 편할듯
• 구름이동과 대각선 확인은 따로 리스트를 만들어서 관리하면 좋겠다.
• 구름 생성시 이전의 구름 위치는 생성하면 안된다. -> 튜플을 사용해서 시간 복잡도를 낮추면 좋겠다.

구현

#  (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 비구름이 생긴다.
# d 방향으로 s칸 이동
# 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙

import sys
input = sys.stdin.readline

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

# 처음 구름 (0-index로!)
clouds = [(N-1, 0), (N-1, 1), (N-2, 0), (N-2, 1)]

# 8방향 (←, ↖, ↑, ↗, →, ↘, ↓, ↙)
mv = [(0, -1), (-1, -1), (-1, 0), (-1, 1),
      (0, 1), (1, 1), (1, 0), (1, -1)]

# 대각선 방향만
deagak = [(-1, -1), (-1, 1), (1, -1), (1, 1)]

for _ in range(M):
    d, s = map(int, input().split())

    # 구름 이동
    new_clouds = []
    for x, y in clouds:
        nx = (x + mv[d-1][0] * s) % N
        ny = (y + mv[d-1][1] * s) % N
        new_clouds.append((nx, ny))
        li[nx][ny] += 1  # 비 내리기
    clouds = new_clouds

    # 물 복사 버그 (대각선 체크)
    for x, y in clouds:
        cnt = 0
        for dx, dy in deagak:
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < N and li[nx][ny] > 0:
                cnt += 1
        li[x][y] += cnt

    # 구름 초기화 및 생성
    prev_clouds = set(clouds)  # 구름이 있었던 자리 기억
    clouds = []

    for i in range(N):
        for j in range(N):
            if li[i][j] >= 2 and (i, j) not in prev_clouds:
                clouds.append((i, j))
                li[i][j] -= 2

print(sum(map(sum, li)))

 

마무리

비구름이 이동한 후 구름 자리를 기억할 때
단순히 리스트로 관리하면 포함 여부를 a in b로 검사할 때 O(N) 시간이 걸려 성능이 나빠진다.
리스트는 mutable 객체라 set에 넣을 수 없지만, 튜플은 immutable이므로 set의 원소로 사용할 수 있다.
따라서 구름 좌표를 튜플로 변환 후 set에 저장하면 포함 여부를 O(1) 로 빠르게 검사할 수 있어 성능이 크게 개선된다.
앞으로 리스트 안의 리스트를 검색해야 할 때에는 "튜플 + set" 조합을 떠올리자.

오오
리스트 → set 변환을 통한 탐색 최적화
결국 DB 인덱스처럼 미리 구조를 만들어놓고 빠르게 조회하는 전략과 유사하다.