https://www.acmicpc.net/problem/17406
2020.1.23
내 풀이 1:
N, M, K = map(int,input().split())
origin_arr = [list(map(int, input().split())) for _ in range(N)]
new_arr = [[0] * M for _ in range(N)]
rcs = []
answer = []
def rotation(r, c, s, arr):
global new_arr
for i in range(N):
for j in range(M):
new_arr[i][j] = arr[i][j]
for shell in range(1, s+1):
for x in range(2*shell):
new_arr[r-shell-1+x][c-shell-1] = arr[r-shell+x][c-shell-1]
for x in range(2*shell):
new_arr[r+shell-1][c-shell-1+x] = arr[r+shell-1][c-shell+x]
for x in range(2*shell):
new_arr[r+shell-1-x][c+shell-1] = arr[r+shell-2-x][c+shell-1]
for x in range(2*shell):
new_arr[r-shell-1][c+shell-1-x] = arr[r-shell-1][c+shell-2-x]
def sequence(index, K, table):
global answer
if index == K:
r = rcs[table[0]][0]
c = rcs[table[0]][1]
s = rcs[table[0]][2]
rotation(r, c, s, origin_arr)
for __ in range(1, K):
r = rcs[table[__]][0]
c = rcs[table[__]][1]
s = rcs[table[__]][2]
rotation(r, c, s, new_arr)
result = sum(new_arr[0])
for idx in range(1, N):
if result > sum(new_arr[idx]):
result = sum(new_arr[idx])
answer.append(result)
return
for _ in range(K):
if _ in table:
continue
table.append(_)
sequence(index+1, K, table)
table.remove(_)
for _ in range(K):
r, c, s = map(int, input().split())
rcs.append([r, c, s])
sequence(0, K, [])
print(min(answer))Python3, 오답
샘플이 1개밖에 없는데 샘플은 정답이 나와서 아직 고민 중...
내 풀이 2:
N, M, K = map(int,input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
new_arr = [[0] * M for _ in range(N)]
rcs = []
answer = []
for i in range(N):
for j in range(M):
new_arr[i][j] = arr[i][j]
def rotation(r, c, s, arr):
global new_arr
for i in range(N):
for j in range(M):
new_arr[i][j] = arr[i][j]
for shell in range(1, s+1):
for x in range(2*shell):
new_arr[r-1-shell][c-1-shell+1+x] = arr[r-1-shell][c-1-shell+x]
for x in range(2*shell):
new_arr[r-1-shell+1+x][c-1+shell] = arr[r-1-shell+x][c-1+shell]
for x in range(2*shell):
new_arr[r-1+shell][c-1+shell-1-x] = arr[r-1+shell][c-1+shell-x]
for x in range(2*shell):
new_arr[r-1+shell-1-x][c-1-shell] = arr[r-1+shell-x][c-1-shell]
def sequence(index, K, table):
global answer
if index == K:
r = rcs[table[0]][0]
c = rcs[table[0]][1]
s = rcs[table[0]][2]
rotation(r, c, s, arr)
for __ in range(1, K):
r = rcs[table[__]][0]
c = rcs[table[__]][1]
s = rcs[table[__]][2]
rotation(r, c, s, new_arr)
result = sum(new_arr[0])
for idx in range(1, N):
if result > sum(new_arr[idx]):
result = sum(new_arr[idx])
answer.append(result)
return
for _ in range(K):
if _ in table:
continue
table.append(_)
sequence(index+1, K, table)
table.remove(_)
for _ in range(K):
r, c, s = map(int, input().split())
rcs.append([r, c, s])
sequence(0, K, [])
print(min(answer))Python3, 샘플 오답
잘못 작성했던 rotation함수를 내가 생각했던, 그리고 가독성이 좋게 수정하였다. 그러나 line 37의 rotation은 잘 돌아가는데 line 43의 rotation은 함수 내 new_arr와 arr가 메모리를 공유(shallow copy)되면서 원하는 결과를 출력하지 않았다.
내 풀이 3:
N, M, K = map(int,input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
next_arr = [[0] * M for _ in range(N)]
rcs = []
answer = []
for i in range(N):
for j in range(M):
next_arr[i][j] = arr[i][j]
def rotation(r, c, s, arr):
new_arr = [[0] * M for _ in range(N)]
for i in range(N):
for j in range(M):
new_arr[i][j] = arr[i][j]
for shell in range(1, s+1):
for x in range(2*shell):
new_arr[r-1-shell][c-1-shell+1+x] = arr[r-1-shell][c-1-shell+x]
for x in range(2*shell):
new_arr[r-1-shell+1+x][c-1+shell] = arr[r-1-shell+x][c-1+shell]
for x in range(2*shell):
new_arr[r-1+shell][c-1+shell-1-x] = arr[r-1+shell][c-1+shell-x]
for x in range(2*shell):
new_arr[r-1+shell-1-x][c-1-shell] = arr[r-1+shell-x][c-1-shell]
return new_arr
def sequence(index, K, table):
global answer
if index == K:
r = rcs[table[0]][0]
c = rcs[table[0]][1]
s = rcs[table[0]][2]
next_arr = rotation(r, c, s, arr)
for __ in range(1, K):
r = rcs[table[__]][0]
c = rcs[table[__]][1]
s = rcs[table[__]][2]
next_arr = rotation(r, c, s, next_arr)
result = sum(next_arr[0])
for idx in range(1, N):
if result > sum(next_arr[idx]):
result = sum(next_arr[idx])
answer.append(result)
return
for _ in range(K):
if _ in table:
continue
table.append(_)
sequence(index+1, K, table)
table.remove(_)
for _ in range(K):
r, c, s = map(int, input().split())
rcs.append([r, c, s])
sequence(0, K, [])
print(min(answer))Python3, 2100ms
전역 변수 new_arr를 제거하고 next_arr라는 변수를 새로 만들어서 메모리 공유하는 것을 방지하였다.
2020.11.30
내 풀이:
# 2020.11.30
# 13:20 ~ 13:56
N, M, K = map(int, input().split())
arr = []
for _ in range(N):
row = list(map(int, input().split()))
arr.append(row)
rotations = []
for _ in range(K):
r, c, s = map(int, input().split())
rotations.append((r-1, c-1, s))
visited = [False] * K
answer = 10 ** 9
def action(r, c, s):
for d in range(1, s + 1):
save = arr[r - d][c - d]
for i in range(r - d, r + d):
arr[i][c - d] = arr[i + 1][c - d]
for j in range(c - d, c + d):
arr[r + d][j] = arr[r + d][j + 1]
for i in range(r + d, r - d, -1):
arr[i][c + d] = arr[i - 1][c + d]
for j in range(c + d, c - d, -1):
arr[r - d][j] = arr[r - d][j - 1]
arr[r - d][c - d + 1] = save
def backup(r, c, s):
for d in range(1, s + 1):
save = arr[r - d][c - d]
for j in range(c - d, c + d):
arr[r - d][j] = arr[r - d][j + 1]
for i in range(r - d, r + d):
arr[i][c + d] = arr[i + 1][c + d]
for j in range(c + d, c - d, -1):
arr[r + d][j] = arr[r + d][j - 1]
for i in range(r + d, r - d, -1):
arr[i][c - d] = arr[i - 1][c - d]
arr[r - d + 1][c - d] = save
def rotation():
global answer
if False not in visited:
for i in range(N):
answer = min(answer, sum(arr[i]))
return
for idx in range(K):
if not visited[idx]:
r, c, s = rotations[idx]
visited[idx] = True
action(r, c, s)
rotation()
visited[idx] = False
backup(r, c, s)
rotation()
print(answer)Python3, 740ms
재귀를 이용한 DFS 백트래킹으로 문제를 해결하였다. 재귀 깊이가 최대 6이기 때문에 굳이 스택 형태로 구현할 필요가 없었다. 회전시키는 action함수와 회전했던 부분을 복구시키기 위한 backup함수를 따로 구현하였다. Deep Copy를 이용하는 대신 복구시키는 함수를 따로 구현하였기 때문에 이전보다 실행시간을 단축할 수 있었다.
하루하루 성장하는 개발자