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

백준 인기 문제집에 포함된 "마법사 상어와 토네이도" 문제의 풀이를 담고 있습니다.

 

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

 

 

블로그 목차

 

1. 아이디어

2. 코드

추천글

 

 

아이디어

 

- 사실 구현 문제이기 때문에 뭔가 크게 설명할 부분이 있을지는 모르겠다.

- 정석으로 푼 것 같지는 않고, 조금 지저분하게 풀었다.

 

1) 나선형으로 한 칸씩 탐색하는 방법

- 자세히 보면 규칙이 존재한다.

- N = 5인 맵에서 토네이도가 발생하면 토네이도는 방향대로 다음의 칸 수만큼 이동한다.

- 1 (왼쪽), 1 (아래쪽), 2 (오른쪽), 2 (위쪽), 3 (왼쪽), 3 (아래쪽), 4 (오른쪽), 4 (위쪽), 4 (왼쪽) 순서이다.

- 따라서 나는 move_cnt라는 변수에 한 쪽 방향으로 몇 칸을 이동할지 정해두고, move_cnt < N-1인 경우에는 2번씩 이동하도록 했다.

- 무슨 말이냐면 move_cnt가 1이면 2번의 for문을 통해 왼쪽으로 move_cnt 만큼, 그리고 아래쪽으로 move_cnt 만큼 이동한다.

- 그러면 move_cnt가 4이면 3번의 for문을 통해 오른쪽, 위쪽, 왼쪽으로 move_cnt 만큼 이동하게 된다.

- 이 규칙은 어떤 크기든 항상 동일하며, 마지막에만 N-1의 칸의 이동이 3번 발생한다는 사실을 기억하면 된다.

 

2) 모래의 흩뿌려짐 구현

- 이건 컴퓨터 비전에서 필터를 생각하면서 조금 비슷하게 풀었다.

- 왼쪽, 오른쪽, 위, 그리고 아래 이동마다 서로 다른 필터를 두었다.

- 예를 들어, 왼쪽으로 이동할 경우 Y점을 기준으로 모래의 이동 비율을 저장한 배열을 두고, 오른쪽으로 이동하는 경우, 그리고 위쪽과 아래쪽 각각 모래의 이동 비율을 저장한 배열을 다 따로 둔다.

- 이 배열은 모래의 이동이 5X5 내에서만 이루어지기 때문에 5X5 사이즈이다.

- 아래 코드에서 상단 부분에 filter라는 변수로 정의되어 있는 딕셔너리를 참고하면 된다.

- 주의사항은 나는 a칸에 나머지 모래가 전부 이동한다고 생각해서 나머지 비율인 55%를 두고 풀었는데, 사실 그렇지 않았다.

- 이렇게 계산하면 Y에 10이라는 모래가 있을 때, 55% 이동하면 5만큼의 모래가 a로 이동하는 것으로 계산된다.

- 하지만, 문제에서는 소수점을 버리기 때문에 1%, 5%, 그리고 7% 비율 칸으로 모래가 0씩 이동하므로 10% 칸 두 개로 1씩 이동하고 나면 8의 모래가 남는다. 이 모래가 전부 a로 이동하므로 a에는 8의 모래가 남게 된다!!

- 아래는 왼쪽으로 이동하는 경우 Y점을 기준으로 주변 점들에 얼마 만큼의 비율로 모래가 흩뿌려지는 지를 가지고 있는 배열이다.

0	0	2	0	0
0	10	7	1	0
5	0	0 (Y)	0	0
0	10	7	1	0
0	0	2	0	0

 

- 아래에는 아래쪽으로 이동하는 경우 Y점을 기준으로 주변 점들에 얼마 만큼의 비율로 모래가 흩뿌려지는 지를 가지고 있는 배열이다.

0	0	0	0	0
0	1	0	1	0
2	7	0 (Y)	7	2
0	10	0	10	0
0	0	5	0	0

 

- 위와 같은 형태로 오른쪽과 위쪽으로 이동하는 경우에 따른 비율을 가지고 있는 배열을 생성한다.

 

3) 시간초과 해결

- 최근에 알았는데, Python에서 전역 변수를 사용하면서 푸는 것보다 함수 내에서 지역 변수를 사용하면서 푸는 것이 조금 더 빠르다는 것을 알았다.

- 따라서 해결 과정을 담은 코드를 solution()이라는 메소드로 묶었다.

- 두 번째로는 모래가 흩뿌려질 때, Y칸에 모래가 0이면 모래의 흩뿌려짐을 따지지 않고 그냥 다음 칸으로 넘어가도록 했다.

코드

import sys
import math

def check(x, y):
    if x >= 0 and y >= 0 and x < N and y < N:
        return True
    return False

N = int(sys.stdin.readline())

def solution():
    maps = []
    for i in range(N):
        maps.append(list(map(int, sys.stdin.readline().split())))

    currX = N // 2
    currY = N // 2

    directions = ["left", "down", "right", "up"]
    points = [[0, -1], [1, 0], [0, 1], [-1, 0]]
    filter = {
        "left": [
            [0, 0, 2, 0, 0],
            [0, 10, 7, 1, 0],
            [5, 0, 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, 0, 5],
            [0, 1, 7, 10, 0],
            [0, 0, 2, 0, 0]
        ],
        "down": [
            [0, 0, 0, 0, 0],
            [0, 1, 0, 1, 0],
            [2, 7, 0, 7, 2],
            [0, 10, 0, 10, 0],
            [0, 0, 5, 0, 0]
        ],
        "up": [
            [0, 0, 5, 0, 0],
            [0, 10, 0, 10, 0],
            [2, 7, 0, 7, 2],
            [0, 1, 0, 1, 0],
            [0, 0, 0, 0, 0]
        ]
    }

    move_cnt = 1
    dir = 0
    answer = 0
    while True:
        if move_cnt < N-1:
            for i in range(2):
                for l in range(move_cnt):
                    baseX = currX + points[dir][0]
                    baseY = currY + points[dir][1]
                    d = directions[dir]

                    if maps[baseX][baseY] == 0:
                        currX = baseX
                        currY = baseY
                        continue

                    temp = maps[baseX][baseY]
                    for j in range(5):
                        for k in range(5):
                            nx = baseX + j - 2
                            ny = baseY + k - 2
                            move = int(maps[baseX][baseY] * filter[d][j][k] / 100)
                            temp -= move
                            if not check(nx, ny):
                                answer += move
                            else:
                                maps[nx][ny] += move
                    if check(baseX + points[dir][0], baseY + points[dir][1]):
                        maps[baseX + points[dir][0]][baseY + points[dir][1]] += temp
                    else:
                        answer += temp
                    maps[baseX][baseY] = 0
                    currX = baseX
                    currY = baseY
                dir = (dir + 1) % 4
            move_cnt += 1
        else:
            for i in range(3):
                for l in range(move_cnt):
                    baseX = currX + points[dir][0]
                    baseY = currY + points[dir][1]
                    d = directions[dir]

                    if maps[baseX][baseY] == 0:
                        currX = baseX
                        currY = baseY
                        continue

                    temp = maps[baseX][baseY]
                    for j in range(5):
                        for k in range(5):
                            nx = baseX + j - 2
                            ny = baseY + k - 2
                            move = int(maps[baseX][baseY] * filter[d][j][k] / 100)
                            temp -= move
                            if not check(nx, ny):
                                answer += move
                            else:
                                maps[nx][ny] += move
                    if check(baseX + points[dir][0], baseY + points[dir][1]):
                        maps[baseX + points[dir][0]][baseY + points[dir][1]] += temp
                    else:
                        answer += temp
                    maps[baseX][baseY] = 0
                    currX = baseX
                    currY = baseY
                dir = (dir + 1) % 4
            break
    return answer
print(solution())

 

코드가 조금 더럽다... 초반 부분의 if와 else는 몇 칸을 이동해야 하는지에 따른 분기이기 때문에 if문 부분만 이해한다면 else문 부분을 이해할 필요는 없다. else의 경우는 마지막 부분에서 나선을 N-1칸씩 3번 이동하는 부분을 구현한 것이다.

 

추천글

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