[python] 20057 - 마법사 상어와 토네이도

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

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

 

백준 삼성 문제집에서 정답률이 가장 높은 문제(70.251%)

난이도는 골3 정도

달팽이 문제 연습용도로 좋음!

다른 상어문제 가기 전에 달팽이에 익숙해지는 용도로 다양한 방법으로 여러번 풀어보기

 

---

코드 설명1

1. 입력 받기

2. 토네이도 회전 구현

    -> 무조건 왼쪽으로 회전하다가 이미 방문한 지점 나오면 직진

3. 비율 상하좌우로 구현

4. 토네이도 구현

 

 

※ 주의할 점

• 비율 소수점 버리기
• 토네이도 시작 점에는 모래가 남지 않음(0으로 초기화)
• 시작점 방문 체크 빼먹지 않기

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

# 3. 비율 상하좌우로 구현
left = [(0, -2, 0.05), (-1, -1, 0.1), (-1, 0, 0.07), (-1, 1, 0.01), (-2, 0, 0.02), (1, -1, 0.1), (1, 0, 0.07), (1, 1, 0.01), (2, 0, 0.02), (0, -1, 0)]
right = [(x, -y, d) for x, y, d in left]
up = [(y, -x, d) for x, y, d in left]
down = [(-y, x, d) for x, y, d in left]
dir = {0: left, 1: down, 2: right, 3: up}

# 4. 토네이도 구현
def move(sx, sy, d):
    global ans

    total = board[sx][sy]
    sum = 0

    for x, y, z in dir[d]:
        nx = sx + x
        ny = sy + y
        if z == 0:
            if nx >= N or nx < 0 or ny >= N or ny < 0:
                ans += total - sum
            else:
                board[nx][ny] += (total - sum)
        s = int(total * z)
        sum += s
        if nx >= N or nx < 0 or ny >= N or ny < 0:
            ans += s
        else:
            board[nx][ny] += s

    board[sx][sy] = 0


# 1. 입력 받기
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * N for _ in range(N)]
ans = 0
d = -1
x, y = N//2, N//2
visited[x][y] = True
for i in range(N**2 - 1):
    # 2. 토네이도 회전 구현
    d = (d + 1) % 4
    nx, ny = x + dx[d], y + dy[d]
    if nx == N or nx == -1 or ny == N or ny == -1:
        continue
    if visited[nx][ny]:
        d = (d - 1) % 4
        nx, ny = x + dx[d], y + dy[d]

    visited[nx][ny] = True
    move(nx, ny, d)
    x, y = nx, ny

print(ans)

 

 

---

코드 설명2

1. 입력 받기

2. 토네이도 회전 구현

    -> 좌 - 하 - 우 - 상 방향이 몇 번씩 반복되는지

    -> N * 2 - 1 번의 방향이 있고, 오른쪽 & 왼쪽으로 갈때마다 횟수가 한번씩 증가

    -> 0 1 2 2 3 3 0 0 0 1 1 1 2 2 2 2 3 3 3 3

3. 비율 상하좌우로 구현

4. 토네이도 구현

 

 

※ 주의할 점

• 비율 소수점 버리기
• (안해도 되지만) 마지막에 왼쪽으로 한 번 더 가는 거 막아주기

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

# 3. 비율 상하좌우로 구현
left = [(0, -2, 0.05), (-1, -1, 0.1), (-1, 0, 0.07), (-1, 1, 0.01), (-2, 0, 0.02), (1, -1, 0.1), (1, 0, 0.07), (1, 1, 0.01), (2, 0, 0.02), (0, -1, 0)]
right = [(x, -y, d) for x, y, d in left]
up = [(y, -x, d) for x, y, d in left]
down = [(-y, x, d) for x, y, d in left]
dir = {0: left, 1: down, 2: right, 3: up}

# 4. 토네이도 구현
def move(sx, sy, d):
    global ans

    if sy < 0:
        return

    total = board[sx][sy]
    sum = 0

    for x, y, z in dir[d]:
        nx = sx + x
        ny = sy + y
        if z == 0:
            if nx >= N or nx < 0 or ny >= N or ny < 0:
                ans += total - sum
            else:
                board[nx][ny] += (total - sum)
        s = int(total * z)
        sum += s
        if nx >= N or nx < 0 or ny >= N or ny < 0:
            ans += s
        else:
            board[nx][ny] += s

    board[sx][sy] = 0


# 1. 입력 받기
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
ans = 0
x, y = N//2, N//2

time = 0

# 2. 토네이도 회전 구현
for i in range(N * 2 - 1):
    d = i % 4
    if d == 0 or d == 2:
        time += 1

    for _ in range(time):
        nx = x + dx[d]
        ny = y + dy[d]
        move(nx, ny, d)
        x, y = nx, ny


print(ans)

 

 

---

코드 결과