https://www.acmicpc.net/problem/21610
이 문제는 구현 문제입니다.
입력으로 NXN 배열에 저장된 값이 주어지고, 주어진 문제 조건대로 명령을 수행한 후 마지막에 NXN 배열에 저장된 값의 합을 구하는 것이 이 문제의 목표입니다.
접근 방식
1. 입력 값을 입력받기
2. 초기 구름의 위치 정보를 1차원 배열인 cloud_list와 2차원 배열인 cloud_mat에 저장
cloud_list: 구름의 위치 정보(행, 열 값) 저장한 리스트로 구름을 이동시키는 연산을 편하게 하기 위해 사용됨
cloud_mat: 구름이 있는 위치는 True, 없는 위치는 False로 저장한 2차원 리스트로 새로운 구름을 생성하는 연산을 편하게 하기 위해 사용됨
3. 현재 cloud_list에 있는 구름을 이동 주어진 방향으로 이동시킨 후 cloud_list와 cloud_mat을 업데이트
문제에서 주어진 NXN 격자는 1번 행과 N번 행, 1번 열과 N번 열이 연결된 상태이므로,
구름을 이동할 때 아래와 같은 식을 따름
(새로운 행 위치) = ((현재 행 위치) + (이동할 방향) * (이동할 거리)) % N
4. 현재 cloud_list에 저장된 구름 위치에 비를 내림(값 1 증가)
5. 비가 내린 위치 주변 대각선 위치에 물이 저장됐다면, 그 칸의 개수만큼 추가적으로 값 증가
6. 바구니에 물의 양이 2 이상인 위치에 구름 생성
cloud_mat을 이용하면 해당 기능을 O(N^2)으로 구현 가능
7. 명령문이 끝날 때까지 3 ~ 6을 반복
전체 코드
제출 언어: PyPy3
시간: 184ms
import sys
def move(d, s):
global N, dy, dx, cloud_mat, cloud_list
for i in range(len(cloud_list)):
cr, cc = cloud_list[i]
nr, nc = (cr+dy[d-1]*s) % N, (cc+dx[d-1]*s) % N
cloud_list[i] = (nr, nc)
for cloud in cloud_list:
cr, cc = cloud
cloud_mat[cr][cc] = True
def increase_water():
global mat, cloud_list
for cloud in cloud_list:
cr ,cc = cloud
mat[cr][cc] += 1
def increase_extra_water():
global N, mat, dy, dx, cloud_list
for cloud in cloud_list:
cr, cc = cloud
extra_water = 0
for i in range(1, 8, 2):
nr, nc = cr+dy[i], cc+dx[i]
if 0 <= nr < N and 0 <= nc < N and mat[nr][nc] > 0:
extra_water += 1
mat[cr][cc] += extra_water
def create_cloud():
global N, mat, cloud_mat, cloud_list
total = 0
temp_cloud = []
for i in range(N):
for j in range(N):
if cloud_mat[i][j]:
cloud_mat[i][j] = False
elif not cloud_mat[i][j] and mat[i][j] >= 2:
mat[i][j] -= 2
temp_cloud.append([i, j])
total += mat[i][j]
cloud_list = temp_cloud
return total
if __name__ == "__main__":
N, M = map(int, sys.stdin.readline().strip().split())
mat = [ list(map(int, sys.stdin.readline().strip().split())) for _ in range(N) ]
command_list = [ list(map(int, sys.stdin.readline().strip().split())) for _ in range(M) ]
dy, dx = [0, -1, -1, -1, 0, 1, 1, 1], [-1, -1, 0, 1, 1, 1, 0, -1]
cloud_list = [(N-2, 0), (N-2, 1), (N-1, 0), (N-1, 1)]
cloud_mat = [ [ False ] * N for _ in range(N) ]
answer = 0
for command in command_list:
d, s = command
move(d, s)
increase_water()
increase_extra_water()
answer = create_cloud()
print(answer)
읽어 주셔서 감사합니다 :)
틀린 부분이 있다면 댓글로 편히 알려주세요😊
'PS > Python' 카테고리의 다른 글
[백준] 9205 - 맥주 마시면서 걸어가기 (파이썬, Python) (0) | 2021.09.29 |
---|---|
[백준] 1916 - 최소비용 구하기 (파이썬, Python) (0) | 2021.09.28 |
[Programmers] 합승 택시 요금 (파이썬, Python) (0) | 2021.09.21 |
[백준] 1920 - 수 찾기 (파이썬, Python) (0) | 2021.09.19 |
[백준] 2644 - 촌수계산 (파이썬, Python) (0) | 2021.09.17 |