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

문제

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

백준 문제집 - 0x0D강 - 시뮬레이션

알고리즘: 시뮬레이션

---

풀이

마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 의미한다.

토네이도를 시전하면 격자의 가운데 칸부터 토네이도의 이동이 시작된다. 토네이도는 한 번에 한 칸 이동한다.
토네이도가 한 칸 이동할 때마다 모래는 다음과 같이 일정한 비율로 흩날리게 된다.

토네이도가 x에서 y로 이동하면, y의 모든 모래가 비율과 α가 적혀있는 칸으로 이동한다. 비율이 적혀있는 칸으로 이동하는 모래의 양은 y에 있는 모래의 해당 비율만큼이고, 계산에서 소수점 아래는 버린다. α로 이동하는 모래의 양은 비율이 적혀있는 칸으로 이동하지 않은 남은 모래의 양과 같다. 모래가 이미 있는 칸으로 모래가 이동하면, 모래의 양은 더해진다. 위의 그림은 토네이도가 왼쪽으로 이동할 때이고, 다른 방향으로 이동하는 경우는 위의 그림을 해당 방향으로 회전하면 된다.
토네이도는 (1, 1)까지 이동한 뒤 소멸한다. 모래가 격자의 밖으로 이동할 수도 있다. 토네이도가 소멸되었을 때, 격자의 밖으로 나간 모래의 양을 구해보자.

 

위 문제에서 말하는 비율은 아래와 같다.

 

 

사실 처음에는 토네이도가 x에 있을때, 모래가 y로 옮겨지고 일정한 비율로 퍼뜨린 뒤 남은 모래는 α로 넘겨주는걸로 이해했고... 덕분에 삽질 좀 했다. 왜 이렇게 이해했는진 아직도 모르겠음;;

 

 

전체적인 과정은 다음과 같다.

1. 토네이도가 x → y 로 이동.
2. 비율에 맞게 퍼뜨림. 만약 격자를 벗어난다면 격자 밖으로 벗어난 모래의 양에 더해줌.
3. 남은 모래를 α로 옮김.

이미 모래가 있던 상황이라면 그 모래와 합친다. 계산은 새롭게 이동되는 모래 기준이다.

 

이 문제에서 중요한 부분은 토네이도가 일정한 규칙으로 회전한다는것이다.

회전하면서 해당 방향을 기준으로 비율 표도 회전한다.

우선 주어진 데이터는 서쪽을 향할때의 비율값이다.

directions = [(0, -1), (1, 0), (0, 1), (-1, 0)]
patterns = {0: [(-2, 0, 0.02), (2, 0, 0.02), (-1, 0, 0.07), (1, 0, 0.07),
               (-1, -1, 0.1), (1, -1, 0.1), (-1, 1, 0.01), (1, 1, 0.01), (0, -2, 0.05)]}

토네이도는 항상 서 → 남 → 동 → 북 순으로 회전하므로 방향값을 0부터 차례대로 지정해둔다.

회전에 따른 비율값은 딕셔너리로 따로 저장해뒀다.

y를 기준으로 삼고 각각의 좌표, 비율값을 기록한다. (α는 따로 계산할거라서 빼뒀음.)

이제 patterns[0]을 가지고 남동북일때를 계산해주면 된다.

 

행렬을 시계방향으로 90º 회전시키는건 해봤는데, 반시계방향으로 하려면 어떻게 해야할까?

방향이 서쪽일때와 남쪽일때를 비교해가며 두들겨보니 (-y, x)로 변경해주면 되었다.

def rotate(pattern):
    """(x, y) => (-y, x) 반시계방향으로 90º 회전"""
    rotated = [(-y, x, per) for x, y, per in pattern]
    return rotated

그럼 서쪽을 놓고 돌렸을땐 남쪽이, 남쪽을 놓고 돌렸을땐 동쪽이, 동쪽을 놓고 돌렸을땐 북쪽이 나오겠다.

# directions 순서와 똑같이
patterns[1] = rotate(patterns[0])
patterns[2] = rotate(patterns[1])
patterns[3] = rotate(patterns[2])

 

이제 비율과 관련된 계산은 다 해뒀으니 메인 로직을 작성하면 된다.

토네이도의 처음 좌표는 격자의 정가운데이다. x, y 모두 N // 2 인 상태에서 시작한다.

그리고 한 방향으로 이동할 수 있는 칸의 수는 1부터 시작한다.

그림을 잘 보면 서, 남 / 동, 북 방향일때 이동하는 칸이 같다.

1, 1 → 2, 2 → 3, 3... 순으로 진행된다.

따라서 while문으로 x, y가 (0, 0)이 아닐때까지 아래 과정을 진행한다.

1. 현재 이동길이만큼 두 번씩 반복.
2. 한번의 반복마다 토네이도를 이동시키고 모래 이동 처리.
3. 현재 좌표를 새로운 좌표로 업데이트.
4. 한번의 반복이 끝났다면 방향 전환 후 두번째 반복 시작.
5. 두번째 반복도 끝났다면 이동길이값을 1 추가.

모래 이동 처리는 함수로 따로 분리해놓았다.

현재 칸의 모래값을 변수로 만들어 저장해두고, patterns[방향값]에 저장되어있는 좌표, 비율값 을 하나씩 순회한다.

현재 좌표와 patterns의 좌표로 새로운 좌표를 생성 후 모래의 비율을 계산한다.

 

만약 새로운 좌표가 격자 범위 내에 존재한다면 새로운 좌표에 계산한 모래를 더해준다. 벗어난다면, 벗어난 모래 값에 더해준다.

범위와 상관없이 뿌리는 모래의 양은 따로 기록해둬야한다.

모두 뿌려준 뒤 남은 모래의 값을 α로 옮겨준다.

α가 범위 내에 위치한 좌표라면 해당 좌표의 모래에 남은 모래를 더해주고, 벗어난다면 벗어난 모래 값에 더해준다.

마지막으로 현재 좌표의 모래에서 뿌려준 모래만큼을 빼준다.

전체 코드

# 메모리: 41308KB / 시간: 880ms
from sys import stdin


input = stdin.readline

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
# 방향값. 서, 남, 동, 북
directions = [(0, -1), (1, 0), (0, 1), (-1, 0)]
# y칸 주변으로 흩어지는 모래의 (x, y, 비율)
patterns = {0: [(-2, 0, 0.02), (2, 0, 0.02), (-1, 0, 0.07), (1, 0, 0.07),
               (-1, -1, 0.1), (1, -1, 0.1), (-1, 1, 0.01), (1, 1, 0.01), (0, -2, 0.05)]}


def rotate(pattern):
    """(x, y) => (-y, x) 반시계방향으로 90º 회전"""
    rotated = [(-y, x, per) for x, y, per in pattern]
    return rotated

# directions 순서와 똑같이
patterns[1] = rotate(patterns[0])
patterns[2] = rotate(patterns[1])
patterns[3] = rotate(patterns[2])

x = y = N//2
length = 1
# outside: 격자 밖으로 뿌려진 모래, dir: 현재 방향값
outside = dir = 0
is_finished = False

def spread(x, y, dir):
    global outside
    
    # 현재 칸의 모래
    sand = graph[x][y]
    # 현재 칸으로부터 뿌려진 모래의 양
    spreaded = 0

    for dx, dy, per in patterns[dir]:
        new_sand = int(sand * per)
        nx, ny = x + dx, y + dy

        # 범위 내라면 해당 좌표에 더해주고, 벗어난다면 outside에 더해준다.
        # 뿌려진 모래의 양은 범위와 상관없이 기록
        if 0 <= nx < N and 0 <= ny < N:
            graph[nx][ny] += new_sand
        else:
            outside += new_sand
        spreaded += new_sand
    
    # 현재 모래의 양에서 뿌려진 모래의 양을 뺀 다음 이 값을 조건에 맞게 더해줌.
    ax, ay = x + directions[dir][0], y + directions[dir][1]
    if 0 <= ax < N and 0 <= ay < N:
        graph[ax][ay] += sand - spreaded
    else:
        outside += sand - spreaded
    
    graph[x][y] -= spreaded


while not is_finished:
    # 두번씩(좌/하, 우/상) length만큼 반복
    for _ in range(2):
        for _ in range(length):
            # x → y 토네이도 이동
            nx, ny = x + directions[dir][0], y + directions[dir][1]
            spread(nx, ny, dir)
            x, y = nx, ny
            # (0, 0)에 도착하면 플래그를 True로 변경 후 break
            if x == 0 and y == 0:
                is_finished = True
                break
        if is_finished:
            break
        # length만큼 이동 후 방향을 90º 틀어줌
        dir = (dir + 1) % 4
    # 두번의 반복이 끝나면 length에 1 더해줌
    length += 1

print(outside)

플래그를 사용해서 좌표 상태를 체크하는 방식으로 풀었는데 보기에 별로다...

그렇다고 exit()을 사용하기엔 좀 그렇다. 더 깔끔한 방법이 있는지 찾아보자.