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

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

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

설명

삼성전자 기출 문제로 8가지 방향을 고려하는 구현 문제이다. 그리고 이어진 격자 즉, 배열이 이어져 있다는 뜻. 배열의 마지막 원소의 다음 원소는 첫 번째 원소가 된다. 따라서 구름을 d방향으로 s만큼 이동하는 경우 다음과 같이 모듈러 연산(%)를 이용하여 적절한 위치로 이동해야 한다. 

nx = (x + dx8[d-1] * s) % n
ny = (y + dy8[d-1] * s) % n

그리고 물복사 버그에서의 격자 경계를 고려해야한다. 즉, 아래에서 "이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다." 이 부분을 고려해여 한다. 따라서 이 경우에는 구름이 이동할 때와 달리 다음과 같이 예외처리를 해줘야한다.

 

# 대각선 방향 정의
dx4 = [-1,-1,1,1]
dy4 = [-1,1,-1,1]
for cloud in next_clouds:
	x, y = cloud[0], cloud[1]
    # 물이 있는 즉, graph[x][y] >= 1 인 바구니의 수를 센다
    count = 0
    for i in range(4):
    	nx = x + dx4[i]
        ny = y + dy4[i]
        if (0 <= nx < n) and (0 <= ny < n) and graph[nx][ny] >= 1:
        	count += 1
    graph[x][y] += count # 바구니의 수만큼 물의 양을 증가 시킨다.

핵심 아이디어

dx8 = [0, -1, -1, -1, 0, 1, 1, 1]
dy8 = [-1, -1, 0, 1, 1, 1, 0, -1]

• 문제에서 제시한 방향대로 구현하는 전형적인 시뮬레이션 문제. 

코드 구현

n, m = map(int, input().split())
graph = []
for _ in range(n):
	graph.append(list(map(int, input().split())))
# 비바라기 시전했을 때 생기는 비구름 좌표
clouds = [(n-1, 0), (n-1, 1), (n-2, 0), (n-2, 1)]
# 구름이 이동하는 8가지 방향 정의
dx8 = [0, -1, -1, -1, 0, 1, 1, 1]
dy8 = [-1, -1, 0, 1, 1, 1, 0, -1]

for _ in range(m): # m회 실행
	d, s = map(int, input().split())
	next_clouds = [] # 비구름 이동후 좌표
	visited = [[False] * n for _ in range(n)] # 이동해서 물 내렸는지 
	# 1. d방향으로 s만큼 이동 후 이동 좌표를 next_clouds 에 담는다.
	for cloud in clouds:
		x, y = cloud[0], cloud[1] # 비구름 좌표
		nx = (x + dx8[d-1] * s) % n # 1번행과 n번행이 이어져 있음
		ny = (y + dy8[d-1] * s) % n # 1번열과 n번열이 이어져 있음
		next_clouds.append((nx,ny))
	# 2. 비내리기
	for cloud in next_clouds:
		x,y = cloud[0], cloud[1]
		graph[x][y] += 1 # 비구름이 있는 바구니의 물의양 1 증가시키기
		visited[x][y] = True # 방문처리-> 물의 양 1 증가 여부
	# 3. 구름 제거
	clouds = []
	# 4. next_clouds에 있는 칸에서 대각선 방향으로 1 거리의 칸에서
	# 물의 양이 바구니의 수만큼 증가
	# 단, 이때는 대각선 방향으로 1번열 & n번열 이어지지 않는다.
	# 대각선 방향 정의
	dx4 = [-1,-1,1,1]
	dy4 = [-1,1,-1,1]
	for cloud in next_clouds:
		x,y = cloud[0], cloud[1]
		# '물이 있는 즉, graph[x][y] >= 1 바구니의 수를 센다'
		count = 0
		for i in range(4):
			nx = x + dx4[i]
			ny = y + dy4[i]
			if (0 <= nx < n) and (0 <= ny < n) and graph[nx][ny] >= 1:
				count += 1
		graph[x][y] += count # 바구니의 수만큼 물의양을 증가 시킨다.
	# 5. 물의 양이 2 이상인 칸에 구름 생성 하기
	for i in range(n):
		for j in range(n):
			# 3에서 구름이 사지진 칸이 아니라는 것 -> 방문한적이 없는 칸
			if graph[i][j] >= 2 and visited[i][j] == False:
            #바구니에 저장된 물의 양이 2 이상인 모든 칸에 "구름이 생기고"
            # 여기서는 물의 양이 1 증가 한 것이 아니기 때문에 True 안해도됨!
				clouds.append((i,j))
                # 물의 양이 2 줄어든다.
				graph[i][j] -= 2
ans = 0
for i in range(n): # 모든 행에 대하여
	ans += sum(graph[i])
print(ans)