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

문제

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

 

문제 풀이

 5 x 5 크기의 토네이도가 방향을 전환하며, 현재 있는 모래에 영향을 미치는 문제이다. 문제를 풀기 위해서는 `상, 하, 좌, 우`로 전환되는 경우의 토네이도에 대해 사전에 초기화가 필요하다.

 

tornado = [
    (None, None, 2, None, None),
    (None, 10, 7, 1, None),
    (5, 'a', None, None, None),
    (None, 10, 7, 1, None),
    (None, None, 2, None, None)
]

temp = [tornado]

for idx in range(3):
    temp.append(list(reversed(list(zip(*temp[-1])))))

 위와 같이, 문제의 주어진 조건에 맞게 `tornado` 리스트를 선언한 후, 반시계 방향으로 회전시킨다. 그리고 다음은 이전의 값을 기준으로 다시 회전시키는 과정을 3번 반복하게 되면 `상, 하, 좌, 우`로 전환되는 토네이도를 구할 수 있다.

 

 토네이도의 초기화 과정이 끝났다면, 단순한 Flood fill 문제와는 달리 나선형으로 돌아나가며 탐색을 진행하여야 한다. 문제에서 규칙은 `좌, 하, 우, 상`으로 움직이며 움직이는 거리는 `하 → 우`, `상 → 좌` 인 경우에 거리가 1씩 증가하게 된다. 즉, 위 그림상에서 빨간색 화살표인 경우와, 노란색 화살표인 경우에 이동하는 거리가 1씩 증가한다.

 

 나머지는 문제에서 요구하는 것과 같이 동작하도록 한다면 문제에서 원하는 답을 찾을 수 있다.

 

코드

from sys import stdin
from copy import deepcopy


def visitable(cur_x, cur_y):
    return 0 <= cur_x < N and 0 <= cur_y < N


def init_tornado():
    global tornado

    temp = [tornado]

    # anti-clockwise
    for idx in range(3):
        temp.append(list(reversed(list(zip(*temp[-1])))))

    tornado = deepcopy(temp)


def spread(cur_tornado, loc):
    global answer, A

    cur_x, cur_y = loc
    # tornado 배열의 위치를 일치시키기 위해 -2씩 감소
    tdx, tdy = cur_x - 2, cur_y - 2

    # 'a'에 들어갈 값을 누적하기 위함
    a = 0
    # 'a'의 위치를 기록
    a_loc = None

    for tx in range(5):
        for ty in range(5):
            nx, ny = tx + tdx, ty + tdy
            # 모래에 영향을 미치지 않는 경우
            if cur_tornado[tx][ty] is None:
                continue
            # 숫자로, 모래가 흩날려 가는 경우
            elif cur_tornado[tx][ty] != 'a':
                cur_sand = (A[cur_x][cur_y] * cur_tornado[tx][ty]) // 100
                if visitable(nx, ny):
                    A[nx][ny] += cur_sand
                else:
                    answer += cur_sand
                a += cur_sand
            # a인 경우, 값을 차후에 반영하기 위해 기록
            else:
                a_loc = (tx, ty)

    # 누적된 'a' 값을 반영
    nx, ny = a_loc[0] + tdx, a_loc[1] + tdy
    cur_sand = A[cur_x][cur_y] - a

    if visitable(nx, ny):
        A[nx][ny] += cur_sand
    else:
        answer += cur_sand

    A[cur_x][cur_y] = 0


if __name__ == '__main__':
    answer = 0

    tornado = [
        (None, None, 2, None, None),
        (None, 10, 7, 1, None),
        (5, 'a', None, None, None),
        (None, 10, 7, 1, None),
        (None, None, 2, None, None)
    ]

    dirs = ((0, -1), (1, 0), (0, 1), (-1, 0))
    N = int(stdin.readline())
    A = [list(map(int, stdin.readline().split())) for _ in range(N)]

    init_tornado()

    dist = 1
    x = y = N // 2

    while True:
        for cur_dir in range(4):
            dx, dy = dirs[cur_dir]
            
            for _ in range(dist):
                next_x, next_y = x + dx, y + dy

                # 토네이도 소멸 지점
                if (next_x, next_y) == (0, -1):
                    print(answer)
                    exit(0)

                spread(tornado[cur_dir], [next_x, next_y])

                x, y = next_x, next_y

            # 거리가 추가되는 것은 2, 4번째인 경우.
            dist += 1 if cur_dir == 1 or cur_dir == 3 else 0