상반기 삼성 오후 1번인가 암튼,,
문제링크
문제설명
마법사 상어는 N*N크기의 격자에서 비바라기를 연습한다. 격자에서 1번행-N번행, 1번열-N번열을 연결되었다.
A[r][c] : (r,c) 칸에 있는 바구니 속 물의 양 (1<=r,c<=N)
상어가 비바라기를 시전하면 (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 비구름이 생긴다.
구름에 대해 M번의 이동을 시전한다. 이동에는 이동방향인 d(1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙)와 이동 거리인 s가 주어진다. 이동은 다음과 같다.
- 모든 구름이 d방향으로 s만큼 이동한다.
- 구름이 이동한 칸에 물이 1 증가한다.
- 구름이 전부 사라진다.
- 2에서 물이 증가한 칸에 대해서 물복사 버그를 시전한다. 대각선 방향 거리 1인 칸에 물이 있는 바구니 수 만큼 (r,c)칸의 물의 양을 증가한다. 이때, 경계가 넘어가는 칸은 거리가 1이 아니다.
- 3에서 구름이 사라지지 않은 칸에 대해서 바구니 물의 양이 2이상인 칸에 구름이 생기고, 물의 양을 2 감소시킨다.
모든 이동이 끝나고 격자에 남은 물의 총 합을 구하시오.
문제 풀이
주어진 흐름대로 구현하면 되는 문제이다.
입력받기
water[i][j]: (i,j)칸 위 바구니에 담긴 물의 양
moves[i]: i번째 이동의 방향과 거리
일때, 입력은 다음과 같다.
N, M = map(int, input().split())
water = []
for _ in range(N):
water.append(list(map(int, input().split())))
moves = []
for _ in range(M):
moves.append(list(map(int, input().split())))
초기 구름의 위치는 문제에서 주어진대로 설정하고, M번의 이동을 구현한다.
# 초기 구름 설정
cloud = [(N-1, 0), (N-1, 1), (N-2, 0), (N-2, 1)]구름의 이동 & 비내리기 & 구름 지우기
격자가 모두 연결되어있기 때문에 방향 d로 s만큼 이동은 다음과 같이 구현한다.
nx, ny = (x+dx[d]*s)%N, (y+dy[d]*s)%N copying = set() # 구름이 이동한 좌표 저장
for _ in range(len(cloud)):
x, y = cloud[0][0], cloud[0][1]
nx, ny = (x+dx[d]*s)%N, (y+dy[d]*s)%N
cloud.append((nx, ny)) # 구름 이동
water[nx][ny] += 1 # 비내리기
cloud.pop(0)
copying.add((nx, ny))
cloud = []구름의 이동 순서 4와 5에서 구름이 이동한 칸을 제외하고 계산하기 때문에 copying set을 이용해서 구름이 이동한 좌표를 저장했다.
물 복사 버그
for x, y in copying:
count = 0
for d in range(2, 9, 2):
nx, ny = x+dx[d], y+dy[d]
if in_bound(nx, ny) and water[nx][ny]>0:
count += 1
water[x][y] += count구름이 이동한 모든 좌표에 대해서 대각선 칸을 검사하고, 물이 있는 칸의 개수만큼 물의 양을 증가한다.
구름 새로 생성
for x in range(N):
for y in range(N):
if water[x][y] >= 2 and (x,y) not in copying:
cloud.append((x,y))
water[x][y] -= 2격자의 칸 중 물이 2 이상, 이번 이동에서 구름 이동 위치가 아닌 칸에 대해 구름을 생성한다.
전체코드
전체 코드는 다음과 같다.
import sys
input = sys.stdin.readline
dx = [0, 0, -1, -1, -1, 0, 1, 1, 1]
dy = [0, -1, -1, 0, 1, 1, 1, 0, -1]
def in_bound(x, y):
if x in range(N) and y in range(N):
return True
return False
N, M = map(int, input().split())
water = []
for _ in range(N):
water.append(list(map(int, input().split())))
moves = []
for _ in range(M):
moves.append(list(map(int, input().split())))
# 초기 구름 설정
cloud = [(N-1, 0), (N-1, 1), (N-2, 0), (N-2, 1)]
# M번 이동시키기
for d, s in moves:
copying = set() # 구름이 이동한 좌표 저장
# 모든 구름 이동시키기 & 비내리기 & 지우기
for _ in range(len(cloud)):
x, y = cloud[0][0], cloud[0][1]
nx, ny = (x+dx[d]*s)%N, (y+dy[d]*s)%N
cloud.append((nx, ny)) # 구름 이동
water[nx][ny] += 1 # 비내리기
cloud.pop(0)
copying.add((nx, ny))
cloud = []
# 물 복사 버그
for x, y in copying:
count = 0
for d in range(2, 9, 2):
nx, ny = x+dx[d], y+dy[d]
if in_bound(nx, ny) and water[nx][ny]>0:
count += 1
water[x][y] += count
# 구름 새로 생성
for x in range(N):
for y in range(N):
if water[x][y] >= 2 and (x,y) not in copying:
cloud.append((x,y))
water[x][y] -= 2
answer = 0
for i in range(N):
answer += sum(water[i])
print(answer)소요시간
40분
삼성 기출 하나남아따, , , , , ,
Hongik CE