BOJ 20057 마법사 상어와 토네이도

알고리즘 공부

문제 보기

아이디어

행렬(2차원 배열) 회전
날아가는 모래의 비율이 저장된 ratio_map을 네 방향으로 미리 회전시켜둔다.

def init_ratio_map():
    '''
    토네이도가 이동하는 네 가지 방향에 따른 비율 맵을 반환한다.
    0: 좌, 1: 하, 2: 우, 3: 상
    '''
    ratio_maps = []
    ratio_map = [[0,0,2,0,0],
                 [0, 10, 7, 1, 0],
                 [5, -1, 0, 0, 0],
                 [0, 10, 7, 1, 0],
                 [0,0,2,0,0]]
    tmp = [[row[i] for i in range(5)] for row in ratio_map]
    for _ in range(4):
        ratio_maps.append(tmp)
        tmp = rotate_left(tmp)
    return ratio_maps

날아가는 모래의 양 계산

def calc_blowing(i,j,sand_map,ratio_map):
    '''
    i, j - 토네이도가 도착한 좌표
    sand_map - 문제에서 주어진 격자
    d - 토네이도의 방향
    ratio_map - 날아가는 모래의 비율이 담긴 리스트
    '''
    A, B = sand_map, ratio_map
    n = len(sand_map)
    sand = sand_map[i][j]
    blowed, blowed_away = 0, 0          # blowed: 이동한 모래의 양, blowed_away: 격자 밖으로 날아간 모래
    alpha_x, alpha_y = -1, -1
    sand_map[i][j] = 0                  # 토네이도가 도착한 곳의 모래는 전부 날아감
    for l in range(5):
        for m in range(5):
            a_x, a_y = l+i-2, m+j-2
            if B[l][m] == -1 :                                # ratio_map의 alpha
                alpha_x, alpha_y = a_x, a_y
                continue
            elif a_x < 0 or a_y < 0 or a_x > n-1 or a_y > n-1:    # 격자 밖으로 날아간 모래
                blowed += int(sand*B[l][m]/100)
                blowed_away += int(sand*B[l][m]/100)
            elif 0<=a_x<n and 0<=a_y<n:                       # 밀려난 모래가 추가됨
                blowed += int(sand*B[l][m]/100)
                A[a_x][a_y] += int(sand*B[l][m]/100)
    # alpha가 격자 내부였을 경우
    if 0<=alpha_x<n and 0<=alpha_y<n:
        A[alpha_x][alpha_y] += (sand - blowed)
    # alpha가 격자 밖으로 밀려난 경우
    elif alpha_x<0 or alpha_x>n-1 or alpha_y<0 or alpha_y>n-1:
        blowed_away += (sand - blowed)
    return blowed_away

나선 경로 진행

def move_tornado(sand_map, ratio_maps):
    '''
    토네이도를 이동시키며 격자 밖으로 날아가는 모래의 양을 계산한다.
    sand_map - 문제에서 주어진 모래의 양
    ratio_maps - 이동 방향에 따른 비율 맵 리스트
    '''
    # 좌 하 우 상
    dx, dy = [0, 1, 0, -1], [-1, 0, 1, 0]
    answer = 0
    distance, direction = 1,0
    n = len(sand_map)
    x = y = int(n/2)
    while True:
        # distance만큼 두 번 이동한다
        for i in range(2):
            # direction 방향으로 distance만큼 이동한다
            for j in range(distance):
                x, y = x + dx[direction], y + dy[direction]
                if x == 0 and y == -1:
                    return answer
                answer += calc_blowing(x, y, sand_map, ratio_maps[direction])
            # 방향을 바꾼다
            direction = (direction+1)%4
        distance += 1

debugging

.vimspector.json

{
  "configurations": {
    "vim - run a test": {
      "adapter": "debugpy",
      "filetypes": [ "python" ],
      "configuration": {
        "name": "<name>: Launch",
        "type": "python",
        "request": "launch",
        "cwd": "/Users/mingeun/study/algorithm/BOJ",
        "python": "/opt/homebrew/bin/python3",
        "stopOnEntry": true,
        "console": "externalTerminal",
        "debugOptions": ["-i"],
        "program": "20057.py"
      }
    }
  }
}

debugOptions에 -i를 추가하면 stdin으로부터 입력을 받을 수 있다.

오답 원인

격자점 바깥으로 날아간 모래의 좌표를 검사할 때 n-1이 아니라 n보다 작은 값을 선택했던 것이 원인이였다. 아래의 사진과 같이 n-1로 고쳐야 정답이다.

정답 코드

def rotate_left(matrix):
    '''
    2차원 리스트(정사각 matrix)를 왼쪽으로 90도 회전한 리스트를 반환
    '''
    result = [[0]*5 for _ in range(5)]
    n = len(matrix)
    for i in range(n):
        for j in range(n):
            result[i][j] = matrix[j][n-1-i]
    return result

def init_ratio_map():
    '''
    토네이도가 이동하는 네 가지 방향에 따른 비율 맵을 반환한다.
    0: 좌, 1: 하, 2: 우, 3: 상
    '''
    ratio_maps = []
    ratio_map = [[0,0,2,0,0],
                 [0, 10, 7, 1, 0],
                 [5, -1, 0, 0, 0],
                 [0, 10, 7, 1, 0],
                 [0,0,2,0,0]]
    tmp = [[row[i] for i in range(5)] for row in ratio_map]
    for _ in range(4):
        ratio_maps.append(tmp)
        tmp = rotate_left(tmp)
    return ratio_maps


def calc_blowing(i,j,sand_map,ratio_map):
    '''
    i, j - 토네이도가 도착한 좌표
    sand_map - 문제에서 주어진 격자
    d - 토네이도의 방향
    ratio_map - 날아가는 모래의 비율이 담긴 리스트
    '''
    A, B = sand_map, ratio_map
    n = len(sand_map)
    sand = sand_map[i][j]
    blowed, blowed_away = 0, 0          # blowed: 이동한 모래의 양, blowed_away: 격자 밖으로 날아간 모래
    alpha_x, alpha_y = -1, -1
    sand_map[i][j] = 0                  # 토네이도가 도착한 곳의 모래는 전부 날아감
    for l in range(5):
        for m in range(5):
            a_x, a_y = l+i-2, m+j-2
            if B[l][m] == -1 :                                # ratio_map의 alpha
                alpha_x, alpha_y = a_x, a_y
                continue
            elif a_x < 0 or a_y < 0 or a_x > n-1 or a_y > n-1:    # 격자 밖으로 날아간 모래
                blowed += int(sand*B[l][m]/100)
                blowed_away += int(sand*B[l][m]/100)
            elif 0<=a_x<n and 0<=a_y<n:                       # 밀려난 모래가 추가됨
                blowed += int(sand*B[l][m]/100)
                A[a_x][a_y] += int(sand*B[l][m]/100)
    # alpha가 격자 내부였을 경우
    if 0<=alpha_x<n and 0<=alpha_y<n:
        A[alpha_x][alpha_y] += (sand - blowed)
    # alpha가 격자 밖으로 밀려난 경우
    elif alpha_x<0 or alpha_x>n-1 or alpha_y<0 or alpha_y>n-1:
        blowed_away += (sand - blowed)
    return blowed_away


def move_tornado(sand_map, ratio_maps):
    '''
    토네이도를 이동시키며 격자 밖으로 날아가는 모래의 양을 계산한다.
    sand_map - 문제에서 주어진 모래의 양
    ratio_maps - 이동 방향에 따른 비율 맵 리스트
    '''
    # 좌 하 우 상
    dx, dy = [0, 1, 0, -1], [-1, 0, 1, 0]
    answer = 0
    distance, direction = 1,0
    n = len(sand_map)
    x = y = int(n/2)
    while True:
        # distance만큼 두 번 이동한다
        for i in range(2):
            # direction 방향으로 distance만큼 이동한다
            for j in range(distance):
                if x == 0 and y == -1:
                    return answer
                x, y = x + dx[direction], y + dy[direction]
                answer += calc_blowing(x, y, sand_map, ratio_maps[direction])
            # 방향을 바꾼다
            direction = (direction+1)%4
        distance += 1

def count_sand(sand_map):
    n = len(sand_map)
    count = 0
    for i in range(n):
        for j in range(n):
            count += sand_map[i][j]
    return count

############################# main #############################
n = int(input())
sand_map = [list(map(int, input().split(' '))) for _ in range(n)]
ratio_maps = init_ratio_map()  
print(move_tornado(sand_map, ratio_maps))