문제 링크
풀이
디버깅 정말 ... 힘들었다.
첫번째는 90도 회전시키는 것이 올바르게 구현되지 않아 힘들었다.
인덱스 별 변하는 위치에 따라 규칙을 찾아서 구현해줄 수도 있지만, 시험 때는 시간이 부족할 수도 있으니 외워두는 것도 좋을 듯하다.
def rotate(x, y, l):
# 회전한 배열 임시 저장
new =[ [0] * l for _ in range(l)]
for i in range(l):
for j in range(l):
new[i][j] = graph[x+l-1-j][y+i]
for i in range(l):
for j in range(l):
graph[x+i][y+j] = new[i][j]
두번째는 얼음의 양 줄일 때 !!!!!!!!!!
순차적으로 줄어들어야 할 얼음을 발견하면 바로 그 때 줄여주었는데, 그러면 이후 탐색 결과에 영향을 주었다..
따라서 줄어들어야할 얼음의 위치를 check라는 배열에 임시로 저장해두고 탐색이 끝난 후 얼음의 크기를 줄여주어야 했다..
전체적인 코드 구현은 조건에 따라 하나씩 따라가면 된다.
아래 과정을 q 만큼 반복
1. 나눠진 부분들에 대해 시계 방향 90도 회전
2. 줄어들어야 할 얼음 위치 저장
3. 얼음 크기 줄이기
남은 얼음의 양은 반복문으로 구하면 되고, 최대 얼음 크기는 bfs 알고리즘으로 구해주면 된다.
from collections import deque
# 얼음 크기 구하기
def bfs(x,y):
q= deque()
q.append((x,y))
# 얼음 크기
cnt = 1
visited[x][y] = True
while q :
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<2**n and 0<=ny<2**n and not visited[nx][ny] and graph[nx][ny]:
visited[nx][ny] = True
q.append((nx,ny))
cnt += 1
return cnt
# 90도 회전 함수
def rotate(x, y, l):
new =[ [0] * l for _ in range(l)]
for i in range(l):
for j in range(l):
new[i][j] = graph[x+l-1-j][y+i]
for i in range(l):
for j in range(l):
graph[x+i][y+j] = new[i][j]
dx = [1,-1,0,0 ]
dy = [0,0,1,-1]
def solve(num):
x = 0
# 모든 격자 부분 시계 방향으로 90도 회전
while x < 2**n:
for i in range(2**n//2**num):
rotate(x, 2**num * i, 2**num)
x += 2**num
# 줄어들어야 할 얼음 위치 임시 저장
check = []
# 줄어들어야 할 얼음 찾기
for i in range(2**n):
for j in range(2**n):
if graph[i][j] > 0 :
cnt = 0
for k in range(4):
nx = i + dx[k]
ny = j + dy[k]
if 0<= nx <2**n and 0 <= ny < 2**n and graph[nx][ny]:
cnt += 1
if cnt < 3 :
check.append((i,j))
# 얼음 크기 줄이기
for i, j in check:
graph[i][j] -= 1
n, q = map(int,input().split())
graph = []
for _ in range(2**n):
graph.append(list(map(int,input().split())))
L = list(map(int,input().split()))
for i in range(q):
solve(L[i])
total = 0
# 남은 얼음의 양
for i in range(2**n):
for j in range(2**n):
total += graph[i][j]
print(total)
visited = [ [False] * 2**n for _ in range(2**n)]
ans = 0
# 최대 얼음 크기 찾기
for i in range(2**n):
for j in range(2**n):
if graph[i][j] and not visited[i][j]:
ans = max(ans, bfs(i,j))
print(ans)
'개발 > algorithm' 카테고리의 다른 글
[백준 21609번] 상어 중학교 - python (0) | 2022.10.06 |
---|---|
[백준 14499번] 주사위 굴리기 - python (0) | 2022.10.06 |
[백준 20057번] 마법사 상어와 토네이도 - python (1) | 2022.10.05 |
[백준 21610번] 마법사 상어와 바비라기 - python (1) | 2022.10.05 |
[백준 21608번] 상어 초등학교 - Python (0) | 2022.10.04 |