21610 마법사 상어와 비바라기
업데이트:
1. 문제
문제는 링크에 들어가면 있다.
2. 정답 코드
문제의 내 정답 코드는 다음과 같다.
"""
기본 정보 설정
"""
# NxN칸, M번 이동
N,M = map(int,input().split())
water_graph = []
for _ in range(N):
water_graph.append(list(map(int,input().split())))
move_info = []
for m in range(M):
move_info.append(list(map(int,input().split())))
# 좌 좌상 상 우상 우 우하 하 좌하
# 1번부터 표현하자.
dc = [0,-1,-1,0,1,1,1,0,-1]
dr = [0,0,-1,-1,-1,0,1,1,1]
"""
M번만큼 이동하는 for문 생성
"""
"""
1. 구름이 d방향으로 s만큼 이동
2. 구름 4칸은 비가내려서 바구니에 저장된 물의 양이 1 증가한다.
3. 구름은 사라진다
4. 2에서 물이 증가한 칸들에서 물복사버그 마법을 사용해서 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼
해당 칸의 물이 증가한다.아, 이동은 1<->N이 됨을 명심하고, 이 물버그는 1<->N이 되지 않는다.
5. 바구니에 저장된 물의양이 2이상인 모든 칸에 구름 생성되고 물의 양이 2줄어듬.
이때 구름이 생기는 곳은 3에서 구름이 사라진 칸이 아니어야한다.
"""
# 위 말그대로 따라하자.
# 일단 구름 visted와 list를 초기화하자.
cloud_visited = [[0 for _ in range(N)] for _ in range(N)]
cloud_list = [[N-1,0],[N-1,1],[N-1-1,0],[N-1-1,1]]
for m,[direction,distance] in enumerate(move_info):
# 구름이 움직이는걸 구현하자. cloud_list를 가지고와서 for문 돌면서 진행할수밖에!
# 이동된 구름으로 인해 물이 증가한 곳에서 물복사버그를 해야하므로, moving cloud의 정보를 저장하는 list도 만들어야한다.
moving_cloud_list = []
for cloud_r,cloud_c in cloud_list :
# 움직인 구름의 위치를 표현해보자.
# %를 잘 활요해야겠다 진짜
moving_cloud_r = (cloud_r + dr[direction]*distance) %N
moving_cloud_c = (cloud_c + dc[direction]*distance) %N
# 그럼 이제 구름의 이동이 끝났다.
# 그럼 비가 내려서 물의 양이 1 증가되도록 하자.
water_graph[moving_cloud_r][moving_cloud_c] += 1
# 움직인 구름의 정보 즉, 물이 추가된 위치의 정보를 가져가자.
moving_cloud_list.append([moving_cloud_r,moving_cloud_c])
# 구름은 사라지지만 이 움직인 위치는 다시 구름이 생성되면 안되니 visited에 추가
cloud_visited[moving_cloud_r][moving_cloud_c] += 1
# 좋아 이렇게되면 이제 구름생성 -> 비내리기 -> 물증가 까지 완료했다.
# 이제 마지막으로 물 복사버그만 완성하면 된다.
# 내용은 다음과 같다.
"""
4. 2에서 물이 증가한 칸들에서 물복사버그 마법을 사용해서 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼
해당 칸의 물이 증가한다.아, 이동은 1<->N이 됨을 명심하고, 이 물버그는 1<->N이 되지 않는다.
"""
# 비가 내려서 물이 증가한 칸들! 즉, moving_cloud_r/c를 아직 사용해야한다.
# 각각을 또 확인해주면서.. 근데 이걸 또 for문을 돌면 너무 비효율적인것 같으니, 위에 이미 사용하고있는 것에 첨가하자. -> 아니야 이거 따로해야되는거야
# 왜냐하면 구름이 물주면서 물의 양의 정보가 바뀔 수 있기 때문에!!
# 움직인 구름들의 위치를 for문으로 가져오자.
for water_r,water_c in moving_cloud_list:
# 비가내린 곳의 대각선 방향들의 dc,dr의 idx는 2,4,6,8이다
# 먼저 복사될 물의 양을 저장하자.
amount_water = 0
# temp_copy_list = []
# moving_cloud_r/c에서 대각선 방향들을 체크하자.
for dd in range(2,9,2):
diagonal_r = water_r + dr[dd]
diagonal_c = water_c + dc[dd]
#여기서 이 대각선 요소들은 0<= 위치 < N을 만족해야만 된다.
if 0<=diagonal_r<N and 0<=diagonal_c<N :
# 해당 위치들에 나중에 물을 추가를 할꺼니까 리스트를 저장해둔다. -> 문제를 잘못 봄
# temp_copy_list.append([diagonal_r,diagonal_c])
# 대각선 요소가 합당할 때, 그 위치에 있는 바구니속 물의 양이 1이상이면 amount_water를 카운트한다.
if water_graph[diagonal_r][diagonal_c] >= 1:
amount_water+=1
# 이제 물 복사 버그를 하기 위해 물의 양도 측정되었고, 복사할 위치들도 저장됬으니 -> 취소,
# 복사를 시작하자.
# 주변에 그럴만한게 없었다면 amount_water가 0이므로 걱정하지말자.
# for copy_r,copy_c in temp_copy_list:
water_graph[water_r][water_c] += amount_water
# 이제 마지막으로 구름을 만들자
"""
5. 바구니에 저장된 물의양이 2이상인 모든 칸에 구름 생성되고 물의 양이 2줄어듬.
"""
# 물의 양이 2 이상인 모든 칸에 구름을 생성한다. 이때 물의 양을 2 줄이고, 이전에 구름이 생성됬던 곳은 배제한다.
# 임시로 새로 만들어질 구름 리스트를 저장하는 리스트를 생성
temp_cloud_list = []
# 여기는 water map을 확인할 수 밖에 없다.
for r in range(N):
for c in range(N):
now_water = water_graph[r][c]
# 물의 양이 2이상인지 확인하고, cloud_list에 없으면 여기는 구름이 생성될 곳이라고 판단하자.
if now_water >= 2 and cloud_visited[r][c] == 0:
# 확인 됬으면, 물의 양을 줄이자.
water_graph[r][c] -= 2
# 임시 구름 리스트에도 추가하자.
temp_cloud_list.append([r,c])
elif cloud_visited[r][c] == 1:
# 아래에서 이걸 아예 처음으로 초기화하지말고,
# 이 조건문을 사용해서 1인걸 0으로 만들자.
# 왜냐하면 r,c가 한번 훑고 지나가면 다시 훑을일이 없기 때문이다.
cloud_visited[r][c] = 0
# 구름 리스트를 업데이트하자
cloud_list = temp_cloud_list
# 다 더하면 끝
results = 0
for n in range(N):
results += sum(water_graph[n])
print(results)
3. 풀이 및 생각
문제 풀이
언제나 그렇듯 시뮬레이션의 핵심은 말을 따라가면서 구현하라!이다. 진짜 그냥 말 그대로 따라서 구현하면 된다. 1부터 5까지 조건을 만족하면서.. 자세한 설명은 주석으로 풀면서 했다.
나의 생각
근데 말끔하게 정리한다고 이번에도 까불면서 순서를 내맘대로하다가 다 풀어놓고 한참을 헤맸다.. 다음부턴 절대로 절대로 저 순서를 지키도록 하자.
여기서 몇가지 짚어야하는 것이 있는데, 하나는 왠만하면 2차원 그래프 visited를 잘 활용하는 것이다. 특히, 매번 visited를 쌩으로 초기화 하는게 아니라, 2중 for문을 도는 일이 생겨서 맵을 다 훑는다면 그때 초기화 하면 좋다!! 그리고 구름의 움직인 위치를 표현할 때.. % 를 쓰는거 진짜ㅜ 최고다 꼭 배우자.