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

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

마법사 상어와 토네이도

문제링크

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

풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
import sys
sys.stdin = open("input.txt",'r')
n = int(input())
board = [[int(x) for x in input().split()] for _ in range(n)]

ans = 0 # 격자 바깥으로 나간 모래의 양

# 바람의 방향에 따른 모래 비율
rate_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]]
rate_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]]
rate_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]]
rate_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]]

# 모래 이동
def spread(ans,board,rate,nx,ny):
    # Y의 좌표를 rate 배열의 좌표와 함께 대응할 수 있도록 좌표이동? 해준다.
    a,b = nx-2, ny-2

    temp = 0 # Y에서 빠져 나간 모래의 총 양
    for i in range(5):
        for j in range(5):
            # 
            if rate[i][j] != 'a' and rate[i][j] != 0:
                if -1 < i+a < n and -1 < j+b < n:
                    board[i+a][j+b] += board[nx][ny]*rate[i][j]//100
                else:
                    # 범위 안에 들어오지 않을 경우
                    ans += board[nx][ny]*rate[i][j]//100
                # a 자리에 모래를 채우기 위해서 빠져나가는 모래의 양을 temp 에 계속 더해준다.
                temp += board[nx][ny]*rate[i][j]//100
            # a 자리의 좌표를 기억
            elif rate[i][j] == 'a':
                remain = (i,j)
    # 나머지 a 부분 처리
    if -1 < remain[0]+a < n and -1 < remain[1]+b < n:
        board[remain[0]+a][remain[1]+b] += board[nx][ny] - temp
    else: # a 자리도 격자 바깥일 경우 격자 바깥으로 나가는 ans에 더해준다.
        ans += board[nx][ny] - temp
    # y 자리 0으로 초기화
    board[nx][ny] = 0
    return board, ans

# 처음 시작 좌표
x,y = n//2,n//2

# 왼쪽 아래 오른쪽 위 
dir = [(0,-1),(1,0),(0,1),(-1,0)]
# 왼 아래 - 오른 오른 위 위 / 왼 왼 왼 아래 아래 아래 - 오른 오른 오른 오른 위 위 위 위
# dir[1]일때랑 dir[3]일때 한 time 씩 늘어난다.
time = 1
flag = 0
while flag != 1:
    for i in range(4):
        dx, dy = dir[i]
        for j in range(time):
            x, y = x+dx, y+dy
            if i == 0: # 왼쪽
                board, ans = spread(ans,board,rate_left,x,y)
            elif i == 1: # 아래
                board, ans = spread(ans,board,rate_down,x,y)
            elif i == 2: # 오른쪽
                board, ans = spread(ans,board,rate_right,x,y)
            elif i == 3: # 위에
                board, ans = spread(ans,board,rate_up,x,y)

            if (x, y) == (0,0): # 0,0 으로 왔을때 종료
                flag = 1
                break
        if i == 1 or i == 3: # 1,3 일때 time 늘려주기
            time += 1
        if flag == 1:
            print(ans)
            break

해설

문제의 핵심은

  • 바람이 부는 방향을 for문으로 어떤식으로 구현해줄지
  • 바람이 부는 방향에 따라 모래가 퍼지는 비율 이차원 배열을 어떤식으로 만들지

이다.

첫번째의 경우, 이중 포문을 사용하여 for i in range(4) 즉 4방향을 돌려주는데 이때, 방향이 아래일때와 위일때 한번씩 time을 증가시 켜줘야 한다. 그래서 이동을 한뒤 i == 3 or i == 1 일때 time += 1 을 하여 두번째 포문에서 다음 첫번째 포문이 돌아갈때 한번씩 더 돌아가게 만들어줬다.

두번째의 경우, 바람이 부는 방향에 따라 모래가 퍼지는 비율은 각 방향에 따라 2차원 배열을 만들었다. 그리고 이동 시작 지점(y의 좌표)를 평행이동? (좌표이동) 해줘서 각 비율에 맞게끔 모래가 퍼지도록 만들었다. 그리고 a 를 만났을때 (나머지) 는 좌표를 remain = (i,j) 로 따로 저장해둔뒤 모든 모래를 퍼뜨리고 맨 마지막에 a 자리에 값을 할당해줬다.

저번에 왼쪽, 오른쪽, 아래, 위 모두 함수를 다 따로따로 만들어서 완전 비효율적으로 만들었었다. 진짜 그때 너무 무식한 방법으로 해서 손이 아플지경… 문제를 생각하고 풀자 ~^^

This post is licensed under CC BY 4.0 by the author.

[Network] 어떻게 DNS 서버가 IP 주소를 조회할까

[Network] 전세계 DNS 서버들은 어떻게 연동할까?

Loading comments from Disqus ...