[백준 20057번] 마법사 상어와 토네이도(파이썬)

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

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

이 문제는 

처음 접했을 때

구현할 것이 상당히 많아 어렵게 느껴집니다.

특히나 이런 류의 문제에 익숙하지 않는다면

좀 많이 빡세게 느껴질 수 있습니다.

 

여기서 조심할 부분은, 알파에 들어갈 값인데요

알파에 들어갈 값이 '이동하지 않은 남은 모래량'

이라는 문구입니다.

잘못 생각한다면

'나머지를 모두 구해보니

45%

그럼 알파는 55%겠네?'

라고 생각하기 쉽습니다.

저도 처음에 그렇게 접근하다가

예시와 다른 답이 도출되었습니다.

 

그 이유는 모래를 뿌릴 때부터 올라갑니다.

모래를 뿌릴 때

'해당 비율만큼이고, 소수점은 버린다'

라고 되어있습니다.

즉, 만약에 10%에서 0,90이 나온다고 하더라도

소수점은 버리므로

0이 되어버립니다.

그러기 때문에 알파에 들어갈 비율은

55%가 아니라

그보다 더 높을 수도 있죠.

위의 케이스대로 10%일 때 0,9라면

알파에는 100가 들어갈 수 있겠죠.

 

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

N = int(input())

s_x, s_y = N // 2, N // 2

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

direct = [
    [[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]],
    [[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]],
    [[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]],
    [[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]],
]
# 0 오른쪽 1 아랫쪽 2왼쪽 3윗쪽
# 알파는 -1로 표현.

dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]

snail_move = []

for i in range(1, N):
    for _ in range(2):
        snail_move.append(i)

snail_move.append(N - 1)

d = 0
sand_out = 0

nx = s_x
ny = s_y

# print(snail_move)
for move in snail_move:
    now = 0
    while now < move:
        ax = 0
        ay = 0
        nx += dx[d]
        ny += dy[d]
        sand = graph[nx][ny]
        temp = sand
        blow = direct[d]
        # print(d)
        for x in range(-2, 3, 1):
            for y in range(-2, 3, 1):
                if blow[x + 2][y + 2] == -1:  # 알파가 있는 지역은 가장 마지막에 계산해서 넘김
                    ax = nx + x
                    ay = ny + y
                    continue
                # 격자를 벗어나는 경우
                if nx + x < 0 or nx + x >= N or ny + y < 0 or ny + y >= N:
                    # print('out')
                    sand_out += (sand * blow[x + 2][y + 2]) // 100
                    temp -= (sand * blow[x + 2][y + 2]) // 100
                else:
                    # 격자 내에 있는 경우
                    graph[nx + x][ny + y] += (sand * blow[x + 2][y + 2]) // 100
                    temp -= (sand * blow[x + 2][y + 2]) // 100
        # 알파 위치의 격자를 확인해준다.
        # 모두 흩뿌리고 남은 것이 알파로 이동.
        if 0 <= ax < N and 0 <= ay < N:
            graph[ax][ay] += temp
        else:
            sand_out += temp

        now += 1
        # print(sand_out)

    d = (d + 1) % 4
    # print(graph)
print(sand_out)

 

저는 direct라는 리스트안에

움직이는 순서대로 구현을 다 해준다음에

움직이는 방향에 따라 흩뿌리는 걸 구현했습니다.

다만, 이 코드는 python3에서는 시간초과가 생겼고

pypy3로 통과했습니다.

 

https://jennnn.tistory.com/67

[백준] 20057. 마법사 상어와 토네이도 / python 파이썬

https://hoyeonkim795.github.io/posts/%EB%A7%88%EB%B2%95%EC%82%AC%EC%83%81%EC%96%B4%EC%99%80%ED%86%A0%EB%84%A4%EC%9D%B4%EB%8F%84/

[백준] #20057 마법사 상어와 토네이도 Python (파이썬)

https://prod.velog.io/@jajubal/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EB%B0%B1%EC%A4%80-20057-%EB%A7%88%EB%B2%95%EC%82%AC-%EC%83%81%EC%96%B4%EC%99%80-%ED%86%A0%EB%84%A4%EC%9D%B4%EB%8F%84

[파이썬]백준 20057 마법사 상어와 토네이도

https://hello-i-t.tistory.com/30

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

 

 

# 20057 마법사 상어와 토네이도
import math

N = int(input())
graph = []
for i in range(N):
    graph.append(list(map(int, input().split())))

answer = 0  # 모래의 양

move_x = [-1, 0, 1, 0]
move_y = [0, 1, 0, -1]  # 좌 하 우 상 순서로 이동하도록 편집.

go = []
for i in range(1, N):
    go.append(i)
    go.append(i)

go.append(N - 1)

start_point = N // 2
now_y = start_point
now_x = start_point
dist = 0  # 화살표 방향

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

for move in go:
    k = 0
    while k < move:
        now_y += move_y[dist]
        now_x += move_x[dist]
        sand = graph[now_y][now_x]
        graph[now_y][now_x] = 0
        k += 1
        temp = 0

        if dist == 0:  # 좌
            for i in range(-2, 3):
                for j in range(-2, 3):
                    if left[i + 2][j + 2] != 'a' and left[i + 2][j + 2] != 0:
                        if 0 <= now_y + i < N and 0 <= now_x + j < N:
                            graph[now_y + i][now_x + j] += (sand * left[i + 2][j + 2] // 100)
                        else:
                            answer += (sand * left[i + 2][j + 2] // 100)
                        temp += (sand * left[i + 2][j + 2] // 100)
                    elif left[i + 2][j + 2] == 'a':
                        remain = (i, j)
            if 0 <= remain[0] + now_y < N and 0 <= remain[1] + now_x < N:
                graph[remain[0] + now_y][remain[1] + now_x] += sand - temp
            else:
                answer += sand - temp


        elif dist == 1:  # 하
            for i in range(-2, 3):
                for j in range(-2, 3):
                    if down[i + 2][j + 2] != 'a' and down[i + 2][j + 2] != 0:
                        if 0 <= now_y + i < N and 0 <= now_x + j < N:
                            graph[now_y + i][now_x + j] += (sand * down[i + 2][j + 2] // 100)
                        else:
                            answer += (sand * down[i + 2][j + 2] // 100)
                        temp += (sand * down[i + 2][j + 2] // 100)
                    elif down[i + 2][j + 2] == 'a':
                        remain = (i, j)
            if 0 <= remain[0] + now_y < N and 0 <= remain[1] + now_x < N:
                graph[remain[0] + now_y][remain[1] + now_x] += sand - temp
            else:
                answer += sand - temp

        elif dist == 2:  # 우
            for i in range(-2, 3):
                for j in range(-2, 3):
                    if right[i + 2][j + 2] != 'a' and right[i + 2][j + 2] != 0:
                        if 0 <= now_y + i < N and 0 <= now_x + j < N:
                            graph[now_y + i][now_x + j] += (sand * right[i + 2][j + 2] // 100)
                        else:
                            answer += (sand * right[i + 2][j + 2] // 100)
                        temp += (sand * right[i + 2][j + 2] // 100)
                    elif right[i + 2][j + 2] == 'a':
                        remain = (i, j)
            if 0 <= remain[0] + now_y < N and 0 <= remain[1] + now_x < N:
                graph[remain[0] + now_y][remain[1] + now_x] += sand - temp
            else:
                answer += sand - temp
        else:  # 상
            for i in range(-2, 3):
                for j in range(-2, 3):
                    if up[i + 2][j + 2] != 'a' and up[i + 2][j + 2] != 0:
                        if 0 <= now_y + i < N and 0 <= now_x + j < N:
                            graph[now_y + i][now_x + j] += (sand * up[i + 2][j + 2] // 100)
                        else:
                            answer += (sand * up[i + 2][j + 2] // 100)
                        temp += (sand * up[i + 2][j + 2] // 100)
                    elif up[i + 2][j + 2] == 'a':
                        remain = (i, j)
            if 0 <= remain[0] + now_y < N and 0 <= remain[1] + now_x < N:
                graph[remain[0] + now_y][remain[1] + now_x] += sand - temp
            else:
                answer += sand - temp

    dist = (dist + 1) % 4

print(answer)

이건 그냥 빡구현버전으로 푼 버전입니다.

가독성 측면에서는 이게 더 안 좋습니다.

딱봐도 코드 길이가 길어보이죠...??

그런데 이건 python3로 통과되네요.ㅎㅎ

아마 direct를 리스트로 전체받으면서 꺼내는 시간이

상하좌우 각각 따로따로 구현해서 받는것보다

시간이 더 걸린다고 보겠습니다.

 

(내용추가-2022.10.14)

dx=[0,1,0,-1]
dy=[-1,0,1,0]


N=int(input())
room=[list(map(int,input().split())) for _ in range(N)]
snail_move=[]
for i in range(1,N):
    snail_move.append(i)
    snail_move.append(i)
snail_move.append(N-1)
out_sand=0

def inside(x,y):
    if x<0 or x>=N or y<0 or y>=N:
        return False

    return True

def spread(nx,ny,dir):
    global out_sand
    #방향에 따라 퍼트리는 거 구현해준다
    now_sand=room[nx][ny]
    #etc에는 남은 알파값을 넣어주는 변수
    etc=now_sand
    room[nx][ny]=0
    if dir==0:
        #5%
        five=(now_sand*5)//100
        if inside(nx,ny-2):
            room[nx][ny-2]+=five
        else:
            out_sand+=five
        etc-=five

        #10% 7% 2% 1%
        ten=(now_sand*10)//100
        seven = (now_sand * 7) // 100
        two = (now_sand * 2) // 100
        one=(now_sand*1)//100
        for p in [-1,1]:
            #10
            if inside(nx+p,ny-1):
                room[nx+p][ny-1]+=ten
            else:
                out_sand+=ten
            #7
            if inside(nx+p,ny):
                room[nx+p][ny]+=seven
            else:
                out_sand+=seven
            #2
            if inside(nx+p*2,ny):
                room[nx+p*2][ny]+=two
            else:
                out_sand+=two
            #1
            if inside(nx+p,ny+1):
                room[nx+p][ny+1]+=one
            else:
                out_sand+=one

            etc-=ten
            etc-=seven
            etc-=two
            etc-=one

        #알파에 나머지 넣기
        if inside(nx,ny-1):
            room[nx][ny-1]+=etc
        else:
            out_sand+=etc

    #아래방향
    elif dir==1:
        # 5%
        five = (now_sand * 5) // 100
        if inside(nx+2, ny):
            room[nx+2][ny] += five
        else:
            out_sand += five
        etc -= five

        # 10% 7% 2% 1%
        ten = (now_sand * 10) // 100
        seven = (now_sand * 7) // 100
        two = (now_sand * 2) // 100
        one = (now_sand * 1) // 100
        for p in [-1, 1]:
            # 10
            if inside(nx + 1, ny +p):
                room[nx + 1][ny +p] += ten
            else:
                out_sand += ten
            # 7
            if inside(nx , ny+p):
                room[nx][ny+p] += seven
            else:
                out_sand += seven
            # 2
            if inside(nx , ny+p*2):
                room[nx][ny+p*2] += two
            else:
                out_sand += two
            # 1
            if inside(nx -1, ny + p):
                room[nx -1][ny + p] += one
            else:
                out_sand += one

            etc -= ten
            etc -= seven
            etc -= two
            etc -= one

        # 알파에 나머지 넣기
        if inside(nx+1, ny):
            room[nx+1][ny] += etc
        else:
            out_sand += etc

    #오른쪽 방향
    elif dir==2:
        #5%
        five=(now_sand*5)//100
        if inside(nx,ny+2):
            room[nx][ny+2]+=five
        else:
            out_sand+=five
        etc-=five

        #10% 7% 2% 1%
        ten=(now_sand*10)//100
        seven = (now_sand * 7) // 100
        two = (now_sand * 2) // 100
        one=(now_sand*1)//100
        for p in [-1,1]:
            #10
            if inside(nx+p,ny+1):
                room[nx+p][ny+1]+=ten
            else:
                out_sand+=ten
            #7
            if inside(nx+p,ny):
                room[nx+p][ny]+=seven
            else:
                out_sand+=seven
            #2
            if inside(nx+p*2,ny):
                room[nx+p*2][ny]+=two
            else:
                out_sand+=two
            #1
            if inside(nx+p,ny-1):
                room[nx+p][ny-1]+=one
            else:
                out_sand+=one

            etc-=ten
            etc-=seven
            etc-=two
            etc-=one

        #알파에 나머지 넣기
        if inside(nx,ny+1):
            room[nx][ny+1]+=etc
        else:
            out_sand+=etc
    #윗방향
    elif dir==3:
        # 5%
        five = (now_sand * 5) // 100
        if inside(nx-2, ny):
            room[nx-2][ny] += five
        else:
            out_sand += five
        etc -= five

        # 10% 7% 2% 1%
        ten = (now_sand * 10) // 100
        seven = (now_sand * 7) // 100
        two = (now_sand * 2) // 100
        one = (now_sand * 1) // 100
        for p in [-1, 1]:
            # 10
            if inside(nx - 1, ny +p):
                room[nx - 1][ny +p] += ten
            else:
                out_sand += ten
            # 7
            if inside(nx , ny+p):
                room[nx][ny+p] += seven
            else:
                out_sand += seven
            # 2
            if inside(nx , ny+p*2):
                room[nx][ny+p*2] += two
            else:
                out_sand += two
            # 1
            if inside(nx +1, ny + p):
                room[nx+1][ny + p] += one
            else:
                out_sand += one

            etc -= ten
            etc -= seven
            etc -= two
            etc -= one

        # 알파에 나머지 넣기
        if inside(nx-1, ny):
            room[nx-1][ny] += etc
        else:
            out_sand += etc



nx,ny=N//2,N//2
d=0
for move in snail_move:
    cnt=0
    while cnt<move:

        nx+=dx[d]
        ny+=dy[d]
        cnt+=1
        if room[nx][ny]>0:
            spread(nx,ny,d)

    d=(d+1)%4
    # for h in range(N):
    #     print(room[h])
    # print(out_sand)
    # print()

print(out_sand)

 

시간,가독성 모두를 잡은 코드.

python3로도 통과가 되네요.

우선, 모래를 퍼트릴때

모래가 있는 칸만 퍼트려도 시간이 확 줄어듭니다.

모래가 없는 칸(0인 칸)은

아무리 퍼트려도 0밖에 더해지지 않는데

굳이 수행할 필요가 없습니다.

 

그 다음은 방향별로 퍼트리는 걸 구했는데

저는 코드 가독성을 높이고자

위와 같이 반복문을 사용해서 최대한 줄여봤습니다.

원래는 1,2,5,7,10,알파

각각 따로따로 넣어주면서 보는 거였는데

1,2,7,10은 코드를 작성하다보니

어라?저거 다 양옆으로 왔다갔다 하잖아?

1,2,7,10 한번에 묶을 수 있겠는데?

하고 코드를 묶었습니다.

 

방향별로 퍼지는 게 비슷해서

저는 왼쪽으로 퍼지는 경우 구현하고

복붙한 후에 방향에 맞게 수정했습니다.

이후 디버깅하면서

좌표 입력이 잘못된 지점들 하나씩 맞춰가면서

노트에 좌표그려보고

코드랑 맞는지 확인해나가면서 풀었습니다.

구현을 보기 좋게 고쳐보니

추후에 문제가 생기더라도

어디서 틀렸는지 한눈에 알 수 있어

쉽게 고칠 수 있었습니다.