오류 찾기
01) 오답
예제 4번부터 오답이 출력되었다.
처음에는 회전이 잘못된 줄 알고 눈으로 계속 찍어보며 확인했다. 아무래도 문제는 없었다.
얼음을 녹이는 부분에서 실수를 했다.
회전이 끝난 후 모든 칸을 다니며 인접 칸을 세고 3보다 작으면 -1을 적용했는데, 바로 적용하면 현재 칸이 이후 칸의 인접 칸에 적용이 될 수 있기 때문에 리스트에 따로 좌표를 저장했다가 모든 칸을 다 훑은 후에 한 번에 -1을 해야 했다.
02) 런타임 에러
예제 정답은 잘 나오지만 런타임 에러가 나와서 2시간 동안 고생했다.
남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수를 출력할 때 고려하지 못한 점이 있었다.
연결되어 있는 덩어리가 하나도 없을 때, 얼음이 하나도 없을 때의 경우를 미쳐 생각하지 못했다.
원래는 리스트로 bfs 결과를 받아서 그 중 가장 큰 값을 return 했지만 아무것도 없는 경우에는 0을 반환해야 한다. 따라서 max_chunk = 0을 갱신하는 방식으로 수정했더니 에러가 나지 않았다.
다른 사람의 정답과 비교해보았다. 회전 시키는 방법, bfs 모두 같은 방식이었는데 그 코드보다 속도가 2배 가량 느렸다.
아마도 다른 사람은 함수로 사용해서 deepcopy를 사용하지 않았지만 나는 deepcopy를 사용해서 느린 것 같다.
참고한 코드 출처 : https://kimjingo.tistory.com/131
감사합니다
어떻게 풀었지만 이해 못함.
부분 보드 90도 회전
nr, nc = i + r, j + c
pr, pc = i + c, j + 2**L - 1 - r
공식을 하나씩 써가면서 찾긴 했지만 설명해보라면 어려울 것 같다.
그저 쓰다보니 규칙이 있어서 규칙이 나오게끔 하는 공식을 어쩌다 썼다.
처음에는 좌표를 돌려서 (r,c) -> (c, 2**L - 1 - r) 까지는 생각했지만
i와 j를 더해주는 것을 생각하지 못하고 노가다로 발견했다.
2시간은 걸린 것 같다.ㅎ
코드
import copy
from collections import deque
N, Q = map(int, input().split())
nA = [list(map(int, input().split())) for _ in range(2**N)]
L_lst = list(map(int, input().split()))
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
for L in L_lst:
A = copy.deepcopy(nA)
# 90도 회전
if L > 0:
for i in range(0, 2**N, 2**L):
for j in range(0, 2**N, 2**L):
for r in range(2**L):
for c in range(2**L):
nr, nc = i + r, j + c
pr, pc = i + c, j + 2**L - 1 - r
nA[pr][pc] = A[nr][nc]
# 얼음 녹이기
melt = []
for r in range(2**N):
for c in range(2**N):
cnt = 0
for i in range(4):
if 0<=r+dr[i]<2**N and 0<=c+dc[i]<2**N:
if nA[r+dr[i]][c+dc[i]] > 0:
cnt += 1
if cnt < 3 and nA[r][c] > 0:
melt.append((r,c))
for r, c in melt:
nA[r][c] -= 1
# bfs
def bfs(sr, sc):
queue = deque([(sr, sc)])
visited[sr][sc] = True
cnt = 1
while queue:
r, c = queue.popleft()
for i in range(4):
nr, nc = r + dr[i], c + dc[i]
if 0<=nr<2**N and 0<=nc<2**N:
if nA[nr][nc] > 0 and not visited[nr][nc]:
queue.append((nr, nc))
visited[nr][nc] = True
cnt += 1
return cnt
max_chunk = 0
visited = [[False] * 2**N for _ in range(2**N)]
for r in range(2**N):
for c in range(2**N):
if not visited[r][c] and nA[r][c] > 0:
chunk = bfs(r, c)
if chunk > max_chunk:
max_chunk = chunk
print(sum(sum(nA, [])))
print(max_chunk)