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

🚩 시뮬레이션, 구현

* 삼성 SW 역량 테스트 기출 문제

 

 

thinking

1. 토네이도 회전 방향 (y의 위치)

2. 방향별 모래 비율 위치

3. a값과 격자 밖의 모래의 양

이렇게 3가지가 문제풀이의 관건이었다. 구현 문제는 말그대로 문제에서 하라는대로 하면 되는데 토네이도 구현이 어려웠다. 

 

1. 토네이도 회전 방향 (y의 위치)

토네이도 도는 방법을 두가지로 구해봤다.
N = 5인 경우, 위의 그림이랑 맨 위 문제에 주황색으로 표시한 것 처럼 총 24번 움직인다.
(왼쪽 오른쪽 위 아래 = 0 1 2 3)

◾  방법 1 - 몫과 나머지로 구하기 (검정색)

→↑(2 3)이 ←↓(0 1)에 비해 한번씩 더 움직이고,  한바퀴 다 돌면 이전보다 한번 더 움직이므로
몫을 회차, 나머지를 dxdy direction (d) 방향으로 설정한 후, d=0 또는 2이면 한번 더 실행

 

◾  방법 2 - [←↓][→↑] 방향 두개씩 묶어서 구하기 (파랭이)

그림에서 파란색으로 묶은것 처럼 왼아래/오위 를 세트로 묶어서 함수 실행

 

마지막 회차에서 숫자가 부족한건 신경 안써도 된다. 어차피 인덱스 밖으로 나가면 종료하도록 코드를 짜면 되기 때문이다.

 

2. 방향별 모래 비율 위치

방향별 모래 비율의 좌표는 그림처럼 방향별로 규칙을 찾아 튜플형태로 묶었다.

a 는 비율이 없기 때문에 다른 비율애들과 구분짓기 위해 0이라고 뒀고, for문을 돌면서 맨 마지막으로 값을 구하기위해 리스트의 맨 마지막에 두었다.

 

 

코드

◾  토네이도 도는 방법 1 - 몫과 나머지로 구하기

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

    if s_y < 0:
        return
        
    # 3. a, out_sand
    total = 0  # a 구하기 위한 변수
    for dx, dy, z in direction:
        nx = s_x + dx
        ny = s_y + dy
        if z == 0:  # a(나머지)
            new_sand = sand[s_x][s_y] - total
        else:  # 비율
            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
        else:  # 범위 밖이면 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
ans = 0
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]

# 1.토네이도 회전 방향(y위치)
dict = {0: left, 1: down, 2: right, 3: up}
time = 0
for i in range(2*N-1):
    # 몫: i//4(타임+1), 나머지:i%4(방향)
    d = i % 4
    if d == 0 or d == 2:  # 다음 회차(d==0) 이거나 right(d==2) 이면 한번 더
        time += 1
    for _ in range(time):
        n_x = s_x + dx[d]
        n_y = s_y + dy[d]
        recount(n_x, n_y, dict[d])  # y좌표, 방향
        s_x, s_y = n_x, n_y

print(ans)

 

◾  토네이도 도는 방법 2 - [←↓][→↑] 두 방향씩 묶어서 구하기

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

    # y좌표 계산 & x좌표 갱신
    for _ in range(time):
        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:  # a(나머지)
                new_sand = sand[s_x][s_y] - total
            else:  # 비율
                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
            else:  # 범위 밖이면 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.토네이도 회전 방향(y위치)
for i in range(1, N + 1):
    if i % 2:
        recount(i, 0, -1, left)
        recount(i, 1, 0, down)
    else:
        recount(i, 0, 1, right)
        recount(i, -1, 0, up)

print(ans)

 

 

위: 방법2 / 아래: 방법1