BOJ - 마법사 상어와 토네이도 20057번 (python)

❓ 문제 - 백준 마법사 상어와 토네이도 20057번 - python 풀이법

 

출처 

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

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

 

 

📝 문제해결법

1. 이 문제는 구현으로 풀었다.

• 격자판의 중심에서 토네이도가 이동했을 때 위치와 방향을 저장하기 위해 1 ~ n*n의 딕셔너리인 b_dict 선언하여 쉽게 접근할 수 있도록 구현하였다. 만약 토네이도가 한바퀴 다 이동하는 것은 딕셔너리의 1 ~ n*n까지의 키로 접근하면 몇 번째 이동의 위치와 방향을 얻을 수 있다.
• b_dict에서 1번은 (격자판 중심이고) ~ 이동을 통해 n*n번은 (격자판의 0,0)를 가리키게 되며, b_dict 키에 맞는 value값은 해당 위치 행,열 값과 다음 이동 방향이다.
• 토네이도가 이동하는 방향은 왼쪽-아래쪽-오른쪽-위쪽 순으로 규칙적으로 움직이며 방향을 바꾸기 까지 이동거리는 1,1,2,2,3,3,4,4,5,5 .... 순으로 아래쪽방향으로 움직이다가 오른쪽 방향으로 바뀔 때 방향을 유지한 채 이동하는 거리가 커지고, 위쪽방향에서 왼쪽방향으로 방향을 바뀔 때 방향을 유지한 채 이동하는 거리가 커진다. 토네이도에 방향을 유지한채 이동하는 거리는 [1, 1, 2, 2, 3, 3, ..., n-1, n-1, n]이다. 이동 거리를 go 리스트에 넣어 b_dict의 값들을 생성할 때 go[g_idx]만큼 이동했으면 방향을 바꾸고 g_idx 값을 1증가 시키고, go[g_idx] 만큼 이동하지 않았으면 해당 방향으로 계속 이동한 nx,ny값과 방향을 b_dict에 넣어준다.
• 1 ~ n*n번의 키값으로 토네이도의 이동을 구현하는데 현재 위치와 움직이려는 방향, 그리고 다음 위치를 딕셔너리에서 가져온 후, 움직이려는 방향과 다음 위치, 그리고 moving() 함수로 모래를 흩날린다.
• 모래를 흩날린 후 격자밖으로 나간 모래의 양 sand를 출력한다.

2. moving()

• 토네이도가 움직이는 방향에 따라 모래가 흩날리는 비율을 left, right, up, down를 이용한다. 토네이도가 이동하면 모래를 흩날리는 위치인 x,y을 기준으로 행은 x-2 ~ x+2, 열은 y-2 ~ y+2을 살펴서 비율에 맞춰 모래를 흩날리면 된다.
• 모래를 흩날리는 양의 알파 부분은 나머지 부분을 비율에 맞춰서 흩날린 후, 남은 양을 옮겨주면 되는데, 우선 나머지 부분을 비율에 맞춰 흩날리기 위해 만약 알파 부분이 오면 해당 알파 부분의 인덱스 a_x, a_y을 저장한다.
• 나머지 비율에 맞춰서 모래를 흩날리기 전 만약 흩날릴 부분이 격자 밖이면 sand에 값을 더해주고,  격자 안이면 해당 인덱스에 맞춰 흩날릴 모래양을 격자판에 더해준다.
• 나머지 부분을 비율에 맞춰 더해주고 남은 양을 알파부분에 더해주기 위해, 우선 알파 부분의 인덱스가 격자 밖이면 sand에 더해주고 격자 안이면 나머지 부분을 비율에 맞춰 더해주고 남은 양을 알파 부분에 더해준다.

3. 문제 풀고 느낀점

• 방향에 따라 모래를 흩날리는 비율이 다른 부분을 함수로 구현하려다가 포기하고 방향에 따른 비율부분을 따로 리스트에 직접 입력하였다. -> ~에 따라 다른 부분을 구현해야할 갯수가 적으면 직접하자...^^
• 토네이도의 움직임을 딕셔너리로 구현하는 부분에 시간을 너무 할애하였다... 이런 토네이도 부분 구현하는 것을 기억해두어 다음에 유사 문제가 나올 때 이용하자

 

 

💻 소스코드

n = int(input())
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]

board = [list(map(int, input().split())) for _ in range(n)]

b_dict = {}

x, y = n // 2, n // 2
s = 1
count = 0
d = 0
go = []
for i in range(1, n):
    go.append(i)
    go.append(i)
go.append(n)
g_idx = 0
b_dict[1] = [x, y, 0]
sand = 0

left = [[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]]
right = [[0,0,2,0,0],[0,1,7,10,0],[0,0,0,-1,5],[0,1,7,10,0],[0,0,2,0,0]]
up = [[0,0,5,0,0],[0,10,-1,10,0],[2,7,0,7,2],[0,1,0,1,0],[0,0,0,0,0]]
down = [[0,0,0,0,0],[0,1,0,1,0],[2,7,0,7,2],[0,10,-1,10,0],[0,0,5,0,0]]

def moving(x, y, a, plus):
    global sand
    a_x, a_y = -1, -1
    remain = 0
    for i in range(-2, 3):
        for j in range(-2, 3):
            if plus[i+2][j+2] == 0 or plus[i+2][j+2] == -1:
                if plus[i+2][j+2] == -1:
                    a_x, a_y = i+2, j+2
                continue
            temp = int(a*(plus[i+2][j+2]/100))
            remain += temp
            if x+i < 0 or x+i >=n or y+j < 0 or y+j >= n:
                sand += temp
            else:
                board[x+i][y+j] += temp
    if 0 <= x+a_x-2 < n and 0<= y+a_y-2 < n:
        board[x+a_x-2][y+a_y-2] += (a-remain)
    else:
        sand += (a-remain)

for i in range(1, n*n):
    nx = x + dx[d]
    ny = y + dy[d]
    count += 1
    x, y = nx, ny
    if count >= go[g_idx]:
        d = (d+1) % 4
        b_dict[i + 1] = [nx, ny, d]
        g_idx += 1
        count = 0
    else:
        b_dict[i+1] = [nx, ny, d]

for i in range(1, n*n):
    x, y, d = b_dict[i]
    nx, ny, nd = b_dict[i+1]
    if d == 0:
        moving(nx, ny, board[nx][ny],left)
    elif d == 1:
        moving(nx, ny, board[nx][ny], down)
    elif d == 2:
        moving(nx, ny, board[nx][ny], right)
    else:
        moving(nx, ny, board[nx][ny], up)
    board[nx][ny] = 0

print(sand)