[Python] 백준, 21610 (구현)

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

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

 

개요

• 오늘 하루는 이 녀석에 부서졌다. (몇 시간을 잡고 씨름하다가 구글링으로 찾은 정다보드와 비교해보니 로직이 같은데 왜 나만...)
• 아직 100% 이해가 안된 것 같음. 어거지로 정답이 나오긴 했지만 아직 의문점이 좀 존재
• 문제 풀이 감 좀 찾으려고 골드 5 구현 문항만 골라 풀었는데, 이제 슬슬 다른 알고리즘 공부도 병행하려 한다.

 

해결 방법

1. dfs, bfs 문항에서 흔히 다루는 초기 방향 설정 배열의 변형 버전이 등장
   • 대각선을 포함하는 8가지 방향 배열 선언
   • 물 복사 버그를 위한 대각선 4가지 방향 배열 선언
2. cloud 와 관련된 배열이 총 3가지 등장하므로 이름에 유의해서 따라와야 함
   • cloud_idx : 초기 비구름의 위치 인덱스를 저장하는 2차원 배열
   • moved_cloud_idx : 주어진 방향과 거리만큼 이동 후의 위치 인덱스를 저장하는 2차원 배열
   • new_cloud_idx : 2 이상의 바구니에 생성된 새로운 비구름 2차원 배열
3. m (입력받은 명령 수)만큼 순회
   • 좌표 이동 로직
     1. 열, 행끼리 연결되어 있는 상황이므로 나누기를 활용해야함
     2. ( 기존 좌표 방향 * 거리 ) % n 의 형식으로 진행
        • 파이썬은 음수의 나눗셈도 지원함
        • 따라서 음수를 고려하고 더해준 n * 50은 굳이 필요없는 내용
   • 좌표 이동시킨 후 moved_cloud_idx 배열에 append
   • 해당 위치 좌표 바구니 + 1
4. moved_cloud_idx 내의 인덱스 순회
   • 사실 여기가 이해가 전혀 안됨 
     • 굳이 순회 한 번 더 돌릴 필요 없이 이동한 좌표 x, y에 대해 물 버그 복사하면 되는 거 아닌가....
   • 4 방향의 대각선 관찰하여 조건 만족시 cnt 에 1추가
   • 해당 위치 좌표 바구니 + cnt
5. 마지막 전체 순회
   • moved_cloud_idx 에 포함되어 있고 바구니 >=2 일 때 새로운 구름 형성
   • 해당 위치 좌표 바구니 -2
   • new_cloud_idx 에 append
6. cloud_idx 갱신

 

Python Code

import sys

n, m = map(int, sys.stdin.readline().split())
basket = []

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

# 구름 이동용 8가지 방향 배열
dx = [0, -1, -1, -1, 0, 1, 1, 1]
dy = [-1, -1, 0, 1, 1, 1, 0, -1]

# 물 복사 버그용 대각선 방향 배열
copy_dx = [-1, -1, 1, 1]
copy_dy = [-1, 1, 1, -1]

# 초기 구름 위치 인덱스
cloud_idx = [[n - 1, 0], [n - 1, 1], [n - 2, 0], [n - 2, 1]]

for _ in range(m):
    i, j = map(int, sys.stdin.readline().split())
    i -= 1
    # n 행, 열과 0 행, 열이 연결되어 있는 상황이므로
    n_dx = dx[i] * j + n * 50
    n_dy = dy[i] * j + n * 50

    moved_cloud_idx = []

    for x, y in cloud_idx:
        x = (x + n_dx) % n
        y = (y + n_dy) % n

        moved_cloud_idx.append([x, y])
        basket[x][y] += 1

        # 물 복사 버그
    for x, y in moved_cloud_idx:
        cnt = 0
        for i in range(4):
            copy_x = x + copy_dx[i]
            copy_y = y + copy_dy[i]

            if (0 <= copy_x < n) and (0 <= copy_y < n):
                if basket[copy_x][copy_y] > 0:
                    cnt += 1
                else:
                    continue

        basket[x][y] += cnt

    new_cloud_idx = []

    for i in range(n):
        for j in range(n):
            if ([i, j] not in moved_cloud_idx) and basket[i][j] >= 2:
                basket[i][j] -= 2
                new_cloud_idx.append([i, j])
            else:
                continue

    cloud_idx = new_cloud_idx

    # debuging

    # for seq in basket:
    #     print(seq)
    # print(cloud_idx)
    # print(moved_cloud_idx)
    # print('\n')

result = 0
for seq in basket:
    result += sum(seq)

print(result)