[python] 백준 21610 - 마법사 상어와 비바라기

출처 : 백준, https://www.acmicpc.net/problem/21610

21610번: 마법사 상어와 비바라기

 

 

먼저, 생각해야 할 부분

 

1. 문제를 단순하게 줄여보자

 

# 구름은 d방향으로 s칸만큼 이동 후 구름이 있는 칸의 물 + 1 => 구름 제거
# 물이 증가한 칸에 대각선 방향으로 거리가 1인 바구니 중 물이 있는 바구니 수만큼 바구니만큼 물 증가
    # 1, N 경계는 취급 X
# 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고 물의 양이 2가 줄어듬.
    # 이 때, 이전에 구름이 사라진 칸은 제외
    
# 이동 완료 후 물의 총 합

 

---

 

풀이

 

def solution(n, m, water_map, order_list):
    direction = dict([[1, (0, -1)],[2, (-1, -1)],[3, (-1, 0)],[4, (-1, 1)],[5, (0, 1)],[6, (1, 1)],[7, (1, 0)],[8, (1, -1)]])

    # 구름의 초기 위치는 (n-1, 0), (n-1, 1), (n-2, 0), (n-2, 1)
    cloud_point = set([(n-1, 0), (n-1, 1), (n-2, 0), (n-2, 1)])

    for d, s in order_list: #100 M
        # 구름 이동
        mr, mc = direction[d]

        move_cloud_point = set()

        for cr, cc in cloud_point: #250 N
            nr = cr + (s % n) * mr
            nc = cc + (s % n) * mc

            if nr < 0:
                nr += n
            elif nr >= n:
                nr -= n

            if nc < 0:
                nc += n
            elif nc >= n:
                nc -= n

            move_cloud_point.add((nr, nc))


        # 구름이 있는 칸 + 1
        for r, c in move_cloud_point: # N
            water_map[r][c] += 1

        # 구름이 있는 칸을 대상으로 물복사 버그
        check_dir = [(1, 1), (1, -1), (-1, -1), (-1, 1)]

        for r, c in move_cloud_point: # N
            in_water_count = 0

            for mr, mc in check_dir:
                nr = r + mr
                nc = c + mc

                if 0 <= nr < n and 0 <= nc < n and water_map[nr][nc] > 0:
                    in_water_count += 1

            water_map[r][c] += in_water_count

        # 구름 생성
        temp_cloud_point = set()

        for i in range(n): #N
            for j in range(n): #N
                # 구름이 생기지 않았으면서, 물의 양이 2인 곳에 구름 생성 후 물이 2만큼 줄어즘
                if water_map[i][j] >= 2 and (i, j) not in move_cloud_point: # O(1)
                    temp_cloud_point.add((i, j))
                    water_map[i][j] -= 2

        cloud_point = temp_cloud_point

    return sum([sum(line) for line in water_map])

n, m = map(int, input().split())
water_map = [list(map(int, input().split())) for _ in range(n)]
order_list = [list(map(int, input().split())) for _ in range(m)]

print(solution(n, m, water_map, order_list))

 

 

---

시간 복잡도

먼저, 가장 최상단의 order_list에 대한 for문에서 M

 

내부로 들어가면,

cloud_point에서 move_cloud를 계산하는 것 N

구름이 있는 칸 +1 N

구름이 있던 칸 물 복사 버그 N

구름 생성 N^2

 

sum return N^2

 

따라서 O((M+1) * N^2)이니까 대략적으로 O(M * N^2)의 시간복잡도를 가진다.

 

알게 된 점

 

시간초과가 왜 났을까?

 

def solution(n, m, water_map, order_list):
    direction = dict([[1, (0, -1)],[2, (-1, -1)],[3, (-1, 0)],[4, (-1, 1)],[5, (0, 1)],[6, (1, 1)],[7, (1, 0)],[8, (1, -1)]])

    # 구름의 초기 위치는 (n-1, 0), (n-1, 1), (n-2, 0), (n-2, 1)
    cloud_point = [(n-1, 0), (n-1, 1), (n-2, 0), (n-2, 1)]

    for d, s in order_list:
        # 구름 이동
        mr, mc = direction[d]

        for i in range(len(cloud_point)):
            cr, cc = cloud_point[i]

            nr = cr + (s % n) * mr
            nc = cc + (s % n) * mc

            if nr < 0:
                nr += n
            elif nr >= n:
                nr -= n

            if nc < 0:
                nc += n
            elif nc >= n:
                nc -= n

            cloud_point[i] = (nr, nc)


        # 구름이 있는 칸 + 1
        for r, c in cloud_point:
            water_map[r][c] += 1

        # 구름이 있는 칸을 대상으로 물복사 버그
        check_dir = [(1, 1), (1, -1), (-1, -1), (-1, 1)]

        for r, c in cloud_point:
            in_water_count = 0

            for mr, mc in check_dir:
                nr = r + mr
                nc = c + mc

                if 0 <= nr < n and 0 <= nc < n and water_map[nr][nc] > 0:
                    in_water_count += 1

            water_map[r][c] += in_water_count

        # 구름 생성
        temp_cloud_point = []

        for i in range(n):
            for j in range(n):
                # 구름이 생기지 않았으면서, 물의 양이 2인 곳에 구름 생성 후 물이 2만큼 줄어즘
                if water_map[i][j] >= 2 and (i, j) not in cloud_point:
                    temp_cloud_point.append((i, j))
                    water_map[i][j] -= 2

        cloud_point = temp_cloud_point

    return sum([sum(line) for line in water_map])

n, m = map(int, input().split())
water_map = [list(map(int, input().split())) for _ in range(n)]
order_list = [list(map(int, input().split())) for _ in range(m)]

print(solution(n, m, water_map, order_list))

 

가장 처음에는 위와 같이 풀었는데 시간 초과가 났다.

이 경우에 시간복잡도를 분석해보면, 다음과 같다

 

먼저, 가장 최상단의 order_list에 대한 for문에서 M

내부로 들어가면,
cloud_point에서 move_cloud를 계산하는 것 N
구름이 있는 칸 +1 N
구름이 있던 칸 물 복사 버그 N
구름 생성 N^3

sum return N^2

 

즉, O(M * N^3)이라는 시간복잡도가 나왔다.

이는 구름 생성에서 not in 연산자를 list에 썼기 때문인데

list 에서 in 연산자를 쓸 경우 시간복잡도가 O(N)으로 이중 for문에 in 연산자로 O(N^3)이 나온 것이다.

이를 set()로 고쳐 in 연산자의 시간복잡도를 O(1)로 만들어 전체 시간복잡도를 O(M * N^2)으로 줄여 통과할 수 있었다.

 

Github

GitHub - bh2980/Algorithm-Problem: 알고리즘 풀이 흔적들