[백준, 삼성 기출] 20057_마법사 상어와 토네이도 (Python)

20057_마법사 상어와 토네이도 (Python)

0. 출처

• 유형 : 시뮬레이션, 삼성 (gold 3)
• 링크 : 20057번: 마법사 상어와 토네이도

1. 기록

• 22/04/23 (토)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 토네이도가 격자의 가운데 부터 시전한다. n 이 홀수여야 함
>> 토네이도의 회전 모양을 코드로 어떻게 표현할 것인가? 규칙성을 찾자
>> n = 5 인 경우
>> 1칸 2번, 2칸 2번, 3칸 2번, 4칸 2번, 5칸 1번 (마지막의 경우 범위를 벗어나면 종료되도록 한다.)

>> 퍼지는 값
>> dx = [-1, 1, -2, 2, 0, -1, 1, -1, 1]
>> dy = [1, 1, 0, 0, -2, 0, 0, -1, -1]

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
5
0 0 0 0 0
0 0 0 0 0
0 10 0 0 0
0 0 0 0 0
0 0 0 0 0

- 예제 출력 1 -
10

- 예제 입력 2 -
5
0 0 0 0 0
0 0 0 0 0
0 100 0 0 0
0 0 0 0 0
0 0 0 0 0

- 예제 출력 2 -
85

- 예제 입력 3 -
7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 0 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7

- 예제 출력 3 -
139

(3) 코드

# 모래 계산하는 함수
def recount(block, dx, dy, direction):
    global ans, s_x, s_y

    # y좌표 계산 & x좌표 갱신
    for _ in range(block):
        s_x += dx
        s_y += dy
        if s_y < 0:  # 범위 밖이면 stop
            break

        # 3. a, out_sand
        total = 0  # a 구하기 위한 변수

        for dx, dy, z in direction:
            nx = s_x + dx
            ny = s_y + dy

            # 원래모래에서 - 퍼진모래 = 이동한 방향에 남은 모래
            if z == 0:
                new_sand = sand[s_x][s_y] - total

            # 퍼지는 모래양에 모래비율을 곱해준다. 
            elif z != 0:
                new_sand = int(sand[s_x][s_y] * z)
                total += new_sand

            if 0 <= nx < N and 0 <= ny < N:   # 인덱스 범위이면 값 갱신
                sand[nx][ny] += new_sand
            elif not(0 <= nx < N and 0 <= ny < N):  # 범위 밖이면 ans 카운트
                ans += new_sand


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

# 2. 방향별 모래 비율 위치
left = [(1, 1, 0.01), (-1, 1, 0.01), (1, 0, 0.07), (-1, 0, 0.07), (1, -1, 0.1),
         (-1, -1, 0.1), (2, 0, 0.02), (-2, 0, 0.02), (0, -2, 0.05), (0, -1, 0)]
right = [(x, -y, z) for x, y, z in left]
down = [(-y, x, z) for x, y, z in left]
up = [(y, x, z) for x, y, z in left]

s_x, s_y = N//2, N//2  # 시작좌표(x좌표)
ans = 0  # out_sand

# 1. 이동하는 칸 수
for block in range(1, N + 1):
    # 움직이는 칸 수가 홀수인 경우
    if block % 2 == 1:
        recount(block, 0, -1, left)
        recount(block, 1, 0, down)

    # 움직이는 칸 수가 짝수인 경우
    elif block % 2 == 0:
        recount(block, 0, 1, right)
        recount(block, -1, 0, up)

print(ans)

(4) 정리

토네이도의 회전방향을 계속 고려해줘야 한다는 점

토네이도 이동방향에 따른 모래가 퍼지는 방향이 다르다는 점

위 두가지가 생각보다 까다로워서 풀이를 찾아봤습니다.

또한 토네이도 이동방향에 따라 모래가 퍼지는 방향을 하드코딩하는 방법 말고는 시간 내에 떠올리지 못했을거 같습니다.

(5) 참고

참고 풀이