2021 상반기 삼성 SW역량테스트 기출문제이다.
이번에 출제된 4문제 중 내 기준 가장 까다롭고 시간이 많이 든 문제였다.. BFS의 효율을 높이기 위한 전략이 필요했다.
완전 구현 문제로 고도의 집중력을 발휘해야 한다.
특별히 사용한 알고리즘은 가장 큰 그룹 찾을 때와 이를 지울 때의 BFS 정도이고, 완전 구현 문제이다.
- 사용 알고리즘 : Simultaion (+ BFS)
- 사용 자료구조 : Max Heap(최대 힙)
- 1번 조건 - "크기가 가장 큰 블록 그룹을 찾는다(BFS(), findMaxGroup() 함수). 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다." 을 만족시키기 위해 최대 힙을 사용했다.
- 여기서, 나의 실수 포인트!(이것 때문에 디버깅으로 2시간 날렸다ㅠ 하)
- 힙에 값이 담기지 않을 경우를 고려해줘야 한다.
- 그러한 경우는 1. 가장 큰 블록 그룹 크기가 2보다 작음 2. 블록 그룹이 없음
- 2번 조건 - "1에서 찾은 블록 그룹의 모든 블록을 제거한다(BFS(), removeBlocks() 함수). 블록 그룹에 포함된 블록의 수를 B라고 했을 때, B**2점을 획득한다."
- removeBlocks(r, c)에 인자로 넣어줄 때, 최대 힙에서 값을 꺼내야 하므로 모두 -가 붙어있기 때문에
- '-'를 꼭 붙여서 인자로 넘겨줘야 한다 removeBlocks(-row, -col)
- 3, 5번 조건 - 중력 구현(gravity() 함수)
- 4번 조건 - 반시계방향으로 90도 회전 구현(turnLeft90() 함수)
- 이처럼 약간의 BFS와 문제 주어진 조건대로 그대로 구현만 하면 된다.
- 자세한 설명은 아래 주석 처리 해두었다.
파이썬 코드는 다음과 같다.
from sys import stdin
input = stdin.readline
from collections import deque
from heapq import heappush, heappop
dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)
# 시작 위치, 시작번호, 그릴 번호
def bfs(sr, sc, num):
temp = A[sr][sc]
Q = deque([(sr, sc)])
visited[sr][sc] = num
blockCnt, rainbowCnt = 1, 0
while Q:
r, c = Q.popleft()
for d in range(4):
nr = r + dr[d]
nc = c + dc[d]
if not (0 <= nr < N and 0 <= nc < N): continue # 격자 밖
# 이미 방문했거나 검은색 블록 / 빈 공간이면
if visited[nr][nc] == num or A[nr][nc] <= -1:
continue
# 같은 숫자이거나 무지개 블록이면
if A[nr][nc] == temp or A[nr][nc] == 0:
visited[nr][nc] = num # 방문 표시
Q.append((nr, nc)) # 큐에 담기
blockCnt += 1 # 블록 갯수 += 1
if A[nr][nc] == 0:
rainbowCnt += 1 # 무지개 블록 갯수
# (가장 큰 블록 그룹 > 무지개 블록 수 많은 것 > 행이 가장 큰 것 > 열이 가장 큰 것)
heappush(pq, (-blockCnt, -rainbowCnt, -sr, -sc))
return
def removeBlocks(sr, sc):
start = A[sr][sc]
A[sr][sc] = -2 # 첫 위치 맵에 -2로 표시(빈 공간)
visited[sr][sc] = -1 # 첫 위치 -1로 방문 표시(visited 재사용)
Q = deque([(sr, sc)])
while Q:
r, c = Q.popleft()
for d in range(4):
nr = r + dr[d]
nc = c + dc[d]
if not (0 <= nr < N and 0 <= nc < N): continue # 격자 밖
# 빈 공간/검은 블록이거나 이미 방문한 곳이면
if A[nr][nc] <= -1 or visited[nr][nc] == -1: continue
# 같은 숫자 블록이거나 무지개 블록이면
if A[nr][nc] == start or A[nr][nc] == 0:
A[nr][nc] = -2 # 지운 곳 표시
visited[nr][nc] = -1 # 방문 표시
Q.append((nr, nc)) # 재탐색을 위해 큐에 담기
def findMaxBlockGroup():
global score, blockGroup
num = 1
for r in range(N):
for c in range(N):
# 검은 블록/빈 공간이거나 무지개 블록이거나 이미 방문했으면
if A[r][c] <= -1 or A[r][c] == 0 or visited[r][c]:
continue
if 1 <= A[r][c] <= M:
bfs(r, c, num)
num += 1
if pq: # 우선순위 큐에 값이 있는 경우에만
blockCnt, rainbowCnt, row, col = heappop(pq) # 최대 힙
if -blockCnt >= 2: # 그룹에 속한 블록의 개수는 2보다 크거나 같아야 함
score += blockCnt ** 2 # 점수 더하기
removeBlocks(-row, -col)
else:
blockGroup = False # 가장 블록 그룹이 2보다 작음 => 불가능
else:
blockGroup = False # 블록 그룹 없음 => 불가능
def gravity():
for c in range(N):
blocks = deque()
sr, sc = N-1, c
for r in range(N-1, -1, -1):
if A[r][c] >= 0: # 블록 or 일반 블록이면
blocks.append(A[r][c]) # 블록 큐에 추가
A[r][c] = -2 # 빈 공간으로 만들기
if A[r][c] == -1:
while blocks: # 큐에 값이 있는 동안 pop하며 해당 열에 값 채우기
A[sr][sc] = blocks.popleft()
sr -= 1
blocks = deque() # 큐 비우기
sr = r-1
if blocks: # 마지막 부분 마저 값 채우기
while blocks:
A[sr][sc] = blocks.popleft()
sr -= 1
def turnLeft90():
newA = []
for c in range(N-1, -1, -1):
col = []
for r in range(N):
col.append(A[r][c])
newA.append(col)
return newA
# main
N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
score = 0
blockGroup = True # 블록 그룹 존재 여부
while True:
visited = [[0] * N for _ in range(N)]
pq = []
findMaxBlockGroup() # 가장 큰 블록그룹 찾기
if not blockGroup: # 종료 조건
break
gravity() # 중력
A = turnLeft90() # 반시계방향으로 90도 회전
gravity() # 중력
print(score)
- 시간 : 264ms / 메모리 :128216 kb(PyPy3 제출)
- 고찰 : 구현력. 오직 구현력을 보는 문제이다. 약간의 효율성까지 고려해 짜다보니 시간이 좀 많이 걸렸다. 고도의 집중력을 발휘해 코드 한줄 한줄 끝까지 쫓아가면서 디버깅에 성공했다. 정말 오래 걸린 문제였다ㅠ 3시간+a(디버깅까지,,) 혼자 힘으로 풀어내 그나마 다행이었지만, 시간이 많이 들어 아쉬웠다. 더 더 빠르고 정확하게 푸는 연습을 해야겠다. 파이팅!
'Problem Solving > boj' 카테고리의 다른 글
[BOJ]1593. 문자 해독(Python) / Sliding Window (0) | 2021.05.05 |
---|---|
[BOJ] 21611. 마법사 상어와 블리자드(Python) / Simulation (0) | 2021.05.04 |
[BOJ] 21608. 상어 초등학교(Python) / Simulation (0) | 2021.04.30 |
[BOJ] 21610. 마법사 상어와 비바라기(Python) / Simulation (0) | 2021.04.30 |
[BOJ] 1747. 소수&팰린드롬(Python) (0) | 2021.04.29 |