테케 다 맞았는데 0%에서 틀렸습니다!가 나오는 문제
문제
2차원 배열로 쌈싸먹는 완벽한 구현문제다
배열 돌려 배열 내려놔 배열 다시 돌려....
풀이
- 블록 그룹 찾기
- 일반 블록 최소 1개
- 검은 블록 포함 x
- 무지개 블록의 개수는 상관 x
- 블록의 조건
- 최소 2개 이상
- 일반 블록의 색은 모두 동일해야 함
- 기준 블록 : 행과 열이 가장 작은 블록(가장 왼쪽 위에 있는 블록)
- 크기가 가장 큰 블록 찾기
- 길이가 가장 긴 블록
- (길이가 같다면) 무지개 블록 개수가 큰 것
- (무지개 블록 개수가 같다면) 기준 블록의 행이 가장 큰 것
- (기준 블록 행도 같다면) 기준 블록 열이 가장 큰 것
- 중력 작용
- 검은색 블록(-1)은 중력의 영향을 받지 않는다
기본적으로 문제에서 알아낼 수 있는 부분은 이렇다.
- 무지개 블록을 기준 블록으로 삼지는 않았는지,
- 무지개 블록을 중복으로 구할 수 없게 되지는 않았는지,
위 2가지 때문에 0퍼에서 터지는 경우가 많은 거 같고 나는 아래에 있는 중복 부분은 처음부터 고려했는데 무지개 블록이 기준이 되는 경우는 고려를 못했었다.
블록 그룹 찾기
일반적인 bfs 그래프 탐색 방식으로 찾았다.
- 방문처리를 2차원 배열 v를 통해서 해결했는데, cnt값을 통해서 각 방문 회차에 따라 분기 처리하는 걸로 하나의 v만을 사용했다.
- 만약 무지개 블록(0)이라면 중복이 가능하기 때문에 이 회차(cnt)에 방문한 게 아니라면 다시 방문할 수 있도록 해준다(v[nr][nc] != cnt)
- 하지만 일반 블록이라면 첫번째로 찾은 블록과 같은 값인지 확인한 후 무조건 처음 방문한 블록일 경우에만(v[nr][nc] == 0)방문할 수 있도록 한다
- 일반 블록 / 무지개 블록을 각각 리스트에 담고 동시에 bfs를 위한 queue 자료구조를 사용하기 위한 리스트로 따로 사용해야 해서 좀 번거롭고 불필요하다고 생각했다
def bfs(i, j, v, cnt):
v[i][j], start = cnt, block[i][j]
q = [(i, j)]
new_blocks, rbw = [(i, j)], []
while q:
r, c = q.pop(0)
for k in range(4):
nr, nc = r+dr[k], c+dc[k]
if -1<nr<N and -1<nc<N and block[nr][nc]>=0:
if block[nr][nc] == 0 and v[nr][nc] != cnt:
v[nr][nc] = cnt
q.append((nr, nc))
rbw.append((nr, nc))
elif block[nr][nc] == start and v[nr][nc] == 0:
v[nr][nc] = cnt
q.append((nr, nc))
new_blocks.append((nr, nc))
new_blocks, rbw = sorted(new_blocks), sorted(rbw)
return new_blocks + rbw, len(rbw)크기가 가장 큰 블록 찾기
- 길이가 2보다 크진 않은지,
- 현재 구해진 최대 블록의 개수보다 더 작진 않은지,
- 기준 블록의 행과 열 비교까지 각각에 대해 전~부 if~elif로 분기처리
def find_blockgroup():
v = [[0]*N for _ in range(N)]
blocks, max_rbw = [(-1, -1)], 0
cnt = 0
for i in range(N):
for j in range(N):
if block[i][j]>0 and not v[i][j]:
cnt += 1
new_blocks, len_rbw = bfs(i, j, v, cnt)
if len(new_blocks) < 2 or len(blocks) > len(new_blocks):
continue
elif len(blocks) == len(new_blocks) and max_rbw > len_rbw:
continue
elif max_rbw == len_rbw and blocks[0][0] > new_blocks[0][0]:
continue
elif blocks[0][0] == new_blocks[0][0] and blocks[0][1] > new_blocks[0][1]:
continue
blocks, max_rbw = new_blocks[:], len_rbw
return blocks블록 그룹찾기+크기가 가장 큰 블록 찾기
한 번에 해결할 수 있는 깔끔한 코드를 찾아서 리팩토링했다 -> 코드
- Q를 pop 하는 방식이 아니라 idx 값을 하나씩 올려서 사용하는 방식으로 이렇게 되면 최종적으로 Q만 반환해도 된다. bfs 처리할 리스트 따로, 값을 반환할 리스트를 따로 받지 않아도 됨
- 무지개 블록은 따로 리스트를 받을 필요가 없고, 개수만 알면 된다.
- 최종적으로 값 비교는 전부 다 분기처리할 필요 없이, 총 개수, 무지개블록의 개수, 기준블록 행, 기준블록 열 값을 반환한 다음에 max 처리해주면 알아서 비교됨
- 블록 그룹을 알아야 하기 때문에 그 값을 저장한 Q가 max_blocks의 가장 마지막 원소이므로 -1 에 있는 값을 반환
def bfs(si, sj, v, cnt):
v[si][sj], t = cnt, block[si][sj]
Q, idx, rbw = [(si, sj)], 0, 0
while idx < len(Q):
i, j = Q[idx]
for ni, nj in (i-1, j), (i+1, j), (i, j-1), (i, j+1):
if -1<ni<N and -1<nj<N and (b:=block[ni][nj])>=0:
if b == 0 and v[ni][nj] != cnt:
v[ni][nj] = cnt
Q.append((ni, nj))
rbw += 1
elif b==t and v[ni][nj] == 0:
v[ni][nj] = cnt
Q.append((ni, nj))
idx += 1
return [len(Q), rbw, si, sj, Q]
def find_blockgroup():
v = [[0]*N for _ in range(N)]
max_blocks = [0, 0, -1, -1, []]
cnt = 0
for i in range(N):
for j in range(N):
if block[i][j]>0 and not v[i][j]:
cnt += 1
max_blocks = max(max_blocks, bfs(i, j, v, cnt))
return max_blocks[-1]중력 작용
- 아래로 떨어지는 건데 무조건 떨어지는 게 아님
- 기존 배열의 형태는 계속 유지한 상태에서 아래로 값만 떨어져야 함
- -1은 움직이지 않고 -1 위에 있는 값은 -1 위로만 떨어짐
- -2가 배열의 빈공간이라고 가정할 때
기본적으로 0열부터 N-1열까지 비교하는 방식이고, 가장 아래에 있는 행에서부터 위로 올라오는 방식으로 구현.
- 일단은 가장 아래에 있는 행에 bot(bottom; 떨어질 기준 행)이 되는데
- 만약 위로 올라가다가 -1을 만나게 되면 -1위치보다 한 칸 위로 bot값이 바뀌게 되고,
- 0이상의 숫자를 만나게 되면 떨어트리면 되는데
- 단, 같거나 bot의 위치가 더 작을 땐 떨어트릴 필요가 없음.
- bot의 위치가 더 크다면 bot의 위치로 숫자를 옮기고 원래 숫자의 위치에 -2, bot의 위치는 채워졌으므로 한 칸 위로 올림
# 중력 작용
def gravity(arr):
for j in range(N):
bot = i = N-1
while -1<i:
t = arr[i][j]
if t == -1:
bot = i-1
elif t>=0:
if bot > i:
arr[bot][j] = t
arr[i][j] = -2
bot -= 1
i -= 1
return arr최종 코드
원래 코드
# 60ms
# 반시계 방향의 회전
def rotate(arr):
return list(map(list, zip(*arr)))[::-1]
# bfs로 블럭 탐색
def bfs(i, j, v, cnt):
v[i][j], start = cnt, block[i][j]
q = [(i, j)]
new_blocks, rbw = [(i, j)], []
while q:
r, c = q.pop(0)
for k in range(4):
nr, nc = r+dr[k], c+dc[k]
if -1<nr<N and -1<nc<N and block[nr][nc]>=0:
if block[nr][nc] == 0 and v[nr][nc] != cnt:
v[nr][nc] = cnt
q.append((nr, nc))
rbw.append((nr, nc))
elif block[nr][nc] == start and v[nr][nc] == 0:
v[nr][nc] = cnt
q.append((nr, nc))
new_blocks.append((nr, nc))
new_blocks, rbw = sorted(new_blocks), sorted(rbw)
return new_blocks + rbw, len(rbw)
# 블럭의 집합 찾기
def find_blockgroup():
v = [[0]*N for _ in range(N)]
blocks, max_rbw = [(-1, -1)], 0
cnt = 0
for i in range(N):
for j in range(N):
if block[i][j]>0 and not v[i][j]:
cnt += 1
new_blocks, len_rbw = bfs(i, j, v, cnt)
if len(new_blocks) < 2 or len(blocks) > len(new_blocks):
continue
elif len(blocks) == len(new_blocks) and max_rbw > len_rbw:
continue
elif max_rbw == len_rbw and blocks[0][0] > new_blocks[0][0]:
continue
elif blocks[0][0] == new_blocks[0][0] and blocks[0][1] > new_blocks[0][1]:
continue
blocks, max_rbw = new_blocks[:], len_rbw
return blocks
# 그룹 제거 + 점수 합산
def remove(blocks):
global res
res += len(blocks) ** 2
for br, bc in blocks:
block[br][bc] = -2
# 중력 작용
def gravity(arr):
for j in range(N):
bot = i = N-1
while -1<i:
t = arr[i][j]
if t == -1:
bot = i-1
elif t>=0:
if bot > i:
arr[bot][j] = t
arr[i][j] = -2
bot -= 1
i -= 1
return arr
def autoplay():
global block
while 1:
blocks = find_blockgroup()
if len(blocks) == 1:
return
remove(blocks)
gravity(block)
block = gravity(rotate(block))
N, M = map(int, input().split())
block = [list(map(int, input().split())) for _ in range(N)]
dr, dc = (0, 1, 0, -1), (-1, 0, 1, 0)
res = 0
autoplay()
print(res)리팩토링 코드
# 60ms
def rotate(arr):
return list(map(list, zip(*arr)))[::-1]
def bfs(si, sj, v, cnt):
v[si][sj], t = cnt, block[si][sj]
Q, idx, rbw = [(si, sj)], 0, 0
while idx < len(Q):
i, j = Q[idx]
for ni, nj in (i-1, j), (i+1, j), (i, j-1), (i, j+1):
if -1<ni<N and -1<nj<N and (b:=block[ni][nj])>=0:
if b == 0 and v[ni][nj] != cnt:
v[ni][nj] = cnt
Q.append((ni, nj))
rbw += 1
elif b==t and v[ni][nj] == 0:
v[ni][nj] = cnt
Q.append((ni, nj))
idx += 1
return [len(Q), rbw, si, sj, Q]
def find_blockgroup():
v = [[0]*N for _ in range(N)]
max_blocks = [0, 0, -1, -1, []]
cnt = 0
for i in range(N):
for j in range(N):
if block[i][j]>0 and not v[i][j]:
cnt += 1
max_blocks = max(max_blocks, bfs(i, j, v, cnt))
return max_blocks[-1]
def remove(blocks):
global res
res += len(blocks) ** 2
for br, bc in blocks:
block[br][bc] = -2
def gravity(arr):
for j in range(N):
bot = i = N-1
while -1<i:
t = arr[i][j]
if t == -1:
bot = i-1
elif t>=0:
if bot > i:
arr[bot][j] = t
arr[i][j] = -2
bot -= 1
i -= 1
return arr
def autoplay():
global block
while 1:
blocks = find_blockgroup()
if len(blocks) <= 1:
return
remove(blocks)
gravity(block)
block = gravity(rotate(block))
N, M = map(int, input().split())
block = [list(map(int, input().split())) for _ in range(N)]
dr, dc = (0, 1, 0, -1), (-1, 0, 1, 0)
res = 0
autoplay()
print(res)후기
풀고 나니까 그렇게 어려운 거 같진 않은데 구현은 풀수록 문제 해석 능력이 월등하게 중요한 거 같다. 보여지는 것만 읽고 예외상황이랑 고려해야 할 부분들을 빠르게 파악할수록 정확하게 풀 수 있는 거 같당. 물론 난 안 됨 ㅋ
아무말이나하기