[백준/삼성기출] 21610 마법사 상어와 비바라기 Python

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

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

삼성 style의 빡구현 문제 

 

1. 시간초과 난 풀이 

문제점  : [i,j] 좌표가 new_clouds 배열에 속해있는지 확인하는 in 연산이 시간을 많이 잡어먹는다.. 

-> 이를 해결하기 위해서 visited 2차원 배열을 만들어서 방문 여부를 표시한다. 

# 21610 마법사 상어와 비바라기
n, m = map(int, input().split())

# delta 방향
dx = [0, -1, -1, -1, 0, 1, 1, 1]
dy = [-1, -1, 0, 1, 1, 1, 0, -1]

# 대각선 방향
wx = [-1,-1,1,1]
wy = [-1,1,-1,1]
array = []
clouds = [[n-1, 0], [n-1, 1], [n-2, 0], [n-2, 1]] # 구름 위치
answer = 0
for _ in range(n):
    array.append(list(map(int, input().split())))

for _ in range(m):
    d, s = map(int, input().split()) # d방향, s번 이동
    # 구름 이동시키기
    new_clouds = []
    for cloud in clouds:
        cx, cy = cloud[0], cloud[1]
        nx = (cx + dx[d-1] * s) % n
        ny = (cy + dy[d-1] * s) % n
        new_clouds.append([nx, ny])

    # 구름이 있는 칸 물의 양 + 1
    for cloud in new_clouds:
        cx, cy = cloud[0], cloud[1]
        array[cx][cy] += 1

    # 구름 삭제
    clouds = []

    # 물 증가한 칸 대각선 방향 거리1인 칸 바구니 수 만큼 바구니 물 증가
    for cloud in new_clouds:
        count = 0
        cx, cy = cloud[0], cloud[1]
        for k in range(4):
            nx = cx + wx[k]
            ny = cy + wy[k]
            # 대각선 거리 1 에 물있는지 count
            if 0 <= nx < n and 0 <= ny < n:
                if array[nx][ny] > 0:
                    count += 1
        array[cx][cy] += count
    # 물의 양이 2인 칸에 구름이 생긴다. 물의 양이 2 줄어든다
    for i in range(n):
        for j in range(n):
            if array[i][j] >= 2 and [i, j] not in new_clouds:
                clouds.append([i, j])
                array[i][j] -= 2

# 바구니에 들어있는 물의 양의 합
for i in range(n):
    answer += sum(array[i])
print(answer)

 

2.정답 코드 

원소가 배열에 있는지 확인하는 in 연산을 대체해주었더니 시간초과가 해결되었다. 

in 연산자의 시간복잡도는 O(n) 인것에 반해 visited 2차원 배열에서 값 확인하면 O(1) 이 된다.  -> 여기서 시간복잡도를 줄여주었다 

# 21610 마법사 상어와 비바라기
n, m = map(int, input().split())

# delta 방향
dx = [0, -1, -1, -1, 0, 1, 1, 1]
dy = [-1, -1, 0, 1, 1, 1, 0, -1]

# 대각선 방향
wx = [-1,-1,1,1]
wy = [-1,1,-1,1]
array = []
clouds = [[n-1, 0], [n-1, 1], [n-2, 0], [n-2, 1]] # 구름 위치
answer = 0
for _ in range(n):
    array.append(list(map(int, input().split())))

for _ in range(m):
    d, s = map(int, input().split()) # d방향, s번 이동
    visited = [[False]* n for _ in range(n)]
    # 구름 이동시키기
    new_clouds = []
    for cloud in clouds:
        cx, cy = cloud[0], cloud[1]
        nx = (cx + dx[d-1] * s) % n
        ny = (cy + dy[d-1] * s) % n
        new_clouds.append([nx, ny])
        visited[nx][ny] = True 

    # 구름이 있는 칸 물의 양 + 1
    for cloud in new_clouds:
        cx, cy = cloud[0], cloud[1]
        array[cx][cy] += 1

    # 구름 삭제
    clouds = []

    # 물 증가한 칸 대각선 방향 거리1인 칸 바구니 수 만큼 바구니 물 증가
    for cloud in new_clouds:
        count = 0
        cx, cy = cloud[0], cloud[1]
        for k in range(4):
            nx = cx + wx[k]
            ny = cy + wy[k]
            # 대각선 거리 1 에 물있는지 count
            if 0 <= nx < n and 0 <= ny < n:
                if array[nx][ny] > 0:
                    count += 1
        array[cx][cy] += count
    # 물의 양이 2인 칸에 구름이 생긴다. 물의 양이 2 줄어든다
    for i in range(n):
        for j in range(n):
            if array[i][j] >= 2 and visited[i][j] == False:
                clouds.append([i, j])
                array[i][j] -= 2

# 바구니에 들어있는 물의 양의 합
for i in range(n):
    answer += sum(array[i])
print(answer)