[백준/python] 20057번: 마법사 상어와 토네이도

문제

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

20057번: 마법사 상어와 토네이도

---

문제 요약

N × N 격자로 이루어진 모래밭 가운데서 토네이도가 이동하며 해당 칸에 있는 모래를 흩뿌린다.

 

모래밭을 입력 받고 격자 밖으로 나간 모래의 양을 출력한다.

 

+ 토네이도는 모래밭의 (0, 0) 좌표에서 소멸된다.

---

코드

# 토네이도 이동방향
delta = [(0, -1), (1, 0), (0, 1), (-1, 0)]
# 좌, 하, 우, 상

# 토네이도 방향에 맞춰 비율 배열 변경 -> arr를 반시계방향으로 90도 회전하는 함수
def rotate_90(proportion):
    new_proportion = list(reversed(list(zip(*proportion))))
    # zip은 2차원 배열의 행과 열을 바꾸는 함수
    # reversed는 배열의 순서를 거꾸로 바꾸는 함수
    return new_proportion

p = [[0, 0, 0.02, 0, 0], [0, 0.1, 0.07, 0.01, 0], [0.05, 0, 0, 0, 0], [0, 0.1, 0.07, 0.01, 0], [0, 0, 0.02, 0, 0]]
p1 = rotate_90(p)
p2 = rotate_90(p1)
p3 = rotate_90(p2)
proportions = [p, p1, p2, p3]
# 토네이도 방향에 따른 비율 배열
alphas = [(2, 1), (3, 2), (2, 3), (1, 2)]
# 토네이도 방향에 따른 알파 위치

# 토네이도 + 모래 이동
def solution():
    out_sand = 0 
    # 배열 밖으로 나간 sand
    tr = tc = start 
    # 토네이도 위치 인덱스 -> 시작 지점 부터 시작
    tdir = 0 # 현재 토네이도 방향
    turn = 2 # 토네이도 방향 바꾸는 지표 -> 좌, 하 : 2 /우, 상: 4 
    # 2씩 증가하며
    leng = 0 # 토네이도 직선 길이 (0부터 turn을 2로 나눈 수 만큼 증가하고 다시 0이 되는 것을 반복)
    proportion = proportions[0] # 토네이도 방향에 따른 비율 배열 (시작은 좌)

    # 토네이도가 (0, 0)에 도착할 때까지 이동 
    # 토네이도 이동 -> 모래 이동 -> 토네이도 방향 바꾸기
    while not (tr == 0 and tc == 0):
        # 토네이도 이동
        tr += delta[tdir][0]
        tc += delta[tdir][1]
        leng += 1 # 토네이도 길이 갱신
        sand = arr[tr][tc] # arr의 (tr, tc)에 존재하는 모래 양
        arr[tr][tc] = 0 # 토네이도 위치에 있는 모래는 모두 이동
        left = sand # proportion으로 이동하고 남은 모래 (이동 전)

        # proportion의 y위치와 data의 토네이도 위치를 일치시켜 모래 정보 갱신
        for r in range(5):
            for c in range(5):
                now_sand = int(sand * proportion[r][c])
                left -= now_sand
                if 0 <= tr + r - 2 < N and 0 <= tc + c - 2 < N: 
                # 흩날린 모래의 위치가 arr 배열 안에 있다면
                # 비율 배열에서 중심 위치를 (0, 0)으로 봐야하기 때문에 -2를 해주어야한다.
                    arr[tr + r - 2][tc + c - 2] += now_sand
                    # arr에서 (tr + r - 2, tc + c - 2)는 흩뿌려진 모래의 인덱스
                else: 
                # 불가능 하다면 밖으로 나간 모래
                    out_sand += now_sand

        # alpha 위치에 남은 모래 두기
        if 0 <= tr + alphas[tdir][0] - 2 < N and 0 <= tc + alphas[tdir][1] - 2 < N:
            # (tr + alphas[tdir][0] - 2, tc + alphas[tdir][1] - 2)는 arr에서 알파 위치
            arr[tr + alphas[tdir][0] - 2][tc + alphas[tdir][1] - 2] += left
        else:
            out_sand += left

        # 토네이도 방향 변경
        if leng == turn // 2 or leng == turn:
        # 방향을 바꿔야하면
        # leng == turn // 2는 좌, 우 방향의 마지막 이동일 때
        # leng == turn은 하, 상 방향의 마지막 이동일 때
            tdir = (tdir + 1) % 4
            # 토네이도 이동 방향 변경
            proportion = proportions[tdir] 
            # 토네이도 방향에 따른 비율 좌표 변경
            if leng == turn: 
            # 방향 변경, 방향 + 길이 변경을 돌아가면서 진행한다.
                leng = 0
                turn += 2

    # 토네이도 종료 후 바깥의 모래
    print(out_sand)
    return

N = int(input())
start = N//2 # 토네이도 시작지점 (arr 중앙)
arr = [list(map(int, input().split())) for _ in range(N)]
solution()

---

코드 설명

1. 토네이도의 이동 방향(좌, 하, 우, 상)을 설정하는 방향 배열 delta와 그에 따라 변화하는 비율 배열을 저장하는 배열 proportions, 알파 위치를 저장한 배열 alphas를 설정한다.

 

2. 토네이도가 모래판 arr의 (0, 0)에 도착할 때까지 <토네이도 이동>, <모래 이동>, <토네이도 방향, 길이 변경>을 반복한다.

+ 모래 이동 중 arr의 인덱스를 벗어난 모래의 양은 out_sand 변수에 저장한다.

 

3. 토네이도가 (0, 0)에 도착해 소멸하면, out_sand를 출력한다.