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

문제 링크

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

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

풀이 

구현 문제로, 조건에 맞게 구현만 해주면 된다.

 

cloud 라는 배열에 현재 구름들의 위치를 기록해주고, 아래 과정을 입력된 m개의 명령에 대해 수행한다. 

1. 입력된 방향에 맞게 구름들의 현재 위치를 이동시킨다. 

- 이 때 이동된 방향을 set에 기록하는데, 5번 조건을 검사해주기 위해서이다.

cloud 라는 리스트로 비교했었는데, 시간초과가 떴다... set으로 바꿔주니 통과했다. 

2. cloud에 저장된 구름 별 대각선을 검사하여 물의 양을 증가시켜준다.

3. 기존 cloud 에 저장된 위치가 아니고, 물의 양의 2이상이라면 2를 감소시키고, new_cloud 라는 배열에 추가한다.

4. cloud를 new_cloud로 갱신한다. 

# 대각선 확인 
def magic(cloud):

    tmp_dx = [-1,-1,1,1]
    tmp_dy = [-1, 1, -1, 1]

    for a,b in cloud :
        cnt = 0
        for i in range(4):
            nx = a + tmp_dx[i]
            ny = b + tmp_dy[i]

            if nx < 0 or nx >= n or ny < 0 or ny >= n :
                continue
		
            if graph[nx][ny] > 0 :
                cnt += 1
		# 대각선에 있는 물바구니 개수만큼 증가 
        graph[a][b] += cnt

n, m = map(int,input().split())

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

graph = []

for _ in range(n):
    graph.append(list(map(int,input().split())))

order = []

for _ in range(m):
    order.append(list(map(int,input().split())))

# 구름 위치 저장 
cloud = []
cloud.append([n-1,0])
cloud.append([n-1,1])
cloud.append([n-2,0])
cloud.append([n-2,1])

for k in range(m):
    d, s = order[k]
    d -= 1
    # set으로 비교안하고 리스트로 비교하면 시간초과 발생 
    tmp_set = set()
    
    # 모든 구름 이동
    for j in range(len(cloud)):
        cloud[j][0] = ( cloud[j][0] + dx[d] * s ) % n
        cloud[j][1]  = ( cloud[j][1] + dy[d] * s ) % n
        graph[cloud[j][0]][cloud[j][1]] += 1
        tmp_set.add((cloud[j][0],cloud[j][1]))

    magic(cloud)

    new_cloud  =[]
    for i in range(n):
        for j in range(n):
        	# 기존의 구름 위치가 아니고, 물의 양이 2이상 
            if graph[i][j] >= 2 and (i,j) not in tmp_set:
                graph[i][j] -= 2
                new_cloud.append([i,j])
	# 구름 갱신 
    cloud = new_cloud

ans = 0
for i in graph:
    ans += sum(i)
print(ans)