https://www.acmicpc.net/problem/17822
AC까지 1시간 15분 소요되었다.
삼성 문제는 항상 작은 문제 여러개가 합쳐져 있는 느낌이다. 문제를 꼼꼼하게 읽으면서 작은 문제들로 분해한 후 각개격파하자.
인접하는 예외처리에서 0~M을 벗어나는 경우를 음수만 고려했는데, M을 초과하는 경우에 대해서도 고려해줬어야 했다. python에서는 모듈로 연산으로 처리하는게 이런 두 경우가 자동으로 고려되어서 좋은 것 같다.
zero division error 케이스를 잡지 못했다. 항상 나누기를 연산에서 사용할 때 분모가 혹시 0이 될 수 있는지 크로스체크하자.
완전탐색 DFS, BFS 코드 좀 더 손에 익어야 될 것 같다.
BFS를 손코딩으로 거의 다 적고 코드를 작성하니 훨씬 좋았다. 어떤 변수를 어느 위치에 선언할지 어느정도 잡고 들어가니 혼란이 적었다.
from collections import deque
dx_dy = [(0,1),(0,-1),(1,0),(-1,0)]
def is_valid(x,y):
"""범위 안에 있는지"""
if 0<=x<N and 0<=y<M:
return True
return False
def bfs(x, y, visited):
target_num = maps[x][y] # None 아닌것만 전달됨
queue = deque([(x, y)])
near_x_y_list = [(x, y)]
visited[x][y] = True
while queue:
now_x, now_y = queue.pop()
for dx, dy in dx_dy:
new_x, new_y = now_x + dx, now_y + dy
if new_y < 0: # 음수 처리
new_y += M
elif new_y >= M: # 초과 처리(!처음에 못찾음)
new_y -= M
if is_valid(new_x, new_y) and maps[new_x][new_y] \
and maps[new_x][new_y] == target_num and not visited[new_x][new_y]:
visited[new_x][new_y] = True # 방문처리
queue.append((new_x, new_y))
near_x_y_list.append((new_x, new_y))
return near_x_y_list
def rotate(x,d,k):
"""x의 배수인 원판을 d방향으로 k번 이동시키기"""
for i in range(N):
if ((i+1) % x) == 0: # x의 배수번째
for _ in range(k):
if d == 0: # 시계방향
maps[i].appendleft(maps[i].pop())
else: # 반시계 방향
maps[i].append(maps[i].popleft())
def rebalancing():
"""전체원판에 적힌 수 기준 평균에서 더하고 빼기"""
valid_nums = []
for i in range(N):
for j in range(M):
if maps[i][j]: # None인건 제거된거
valid_nums.append(maps[i][j])
if len(valid_nums) == 0:
return # 모두 None이면(!처음에 못찾음)
avg = sum(valid_nums) / len(valid_nums)
for i in range(N):
for j in range(M):
if maps[i][j]: # None인건 제거된거
if maps[i][j] > avg:
maps[i][j] -= 1
elif maps[i][j] < avg:
maps[i][j] += 1
N, M, T = map(int, input().split())
maps = [deque(map(int, input().split())) for _ in range(N)]
x_d_k = [list(map(int, input().split())) for _ in range(T)]
for x, d, k in x_d_k: # O(50)
# 1. x의 배수인 원판을 d방향으로 k번 이동시키기
rotate(x, d, k)
# 2. 원판에서 인접하면서 같은수 쭉 찾기
total_near_x_y_list = []
visited = [[False]*M for _ in range(N)]
for i in range(N):
for j in range(M):
if maps[i][j] and not visited[i][j]:
near_x_y_list = bfs(i, j, visited)
# print(near_x_y_list)
if len(near_x_y_list) >= 2:
total_near_x_y_list.append(near_x_y_list)
# print(total_near_x_y_list)
# 2-1. 인접하면서 같은 수 모두 지우기
if len(total_near_x_y_list) >= 1:
for near_x_y_list in total_near_x_y_list:
for x, y in near_x_y_list:
maps[x][y] = None
else: # 2-2. 인접하면서 같은 수 없으면 평균 구해서 평균기준 1더하고 빼기
rebalancing()
#print(total_near_x_y_list)
#(maps)
sum = 0
for i in range(N):
for j in range(M):
if maps[i][j]:
sum += maps[i][j]
print(sum)