알고리즘 유형 : BFS
풀이 참고 없이 스스로 풀었나요? : X
https://school.programmers.co.kr/learn/courses/30/lessons/84021
소스 코드(파이썬)
from collections import deque, defaultdict
# 4 방향 인접 노드로 이동
def adj_pos(x, y):
yield x-1, y
yield x+1, y
yield x, y-1
yield x, y+1
# (x, y)가 포함된 퍼즐 조각을 여백을 포함한 직사각형
# 형태로 나타낸 2차원 리스트와 조각의 1x1 칸 개수 합을 리턴
def make_puzzle_frag_and_sum(x, y, table, visited):
# find puzzle location
visited[x][y] = 1
dq = deque([(x, y)])
locations = []
while dq:
now_x, now_y = dq.popleft()
locations.append((now_x, now_y))
for adj_x, adj_y in adj_pos(now_x, now_y):
if not (0 <= adj_x < len(table) and 0 <= adj_y < len(table[0])):
continue
if table[adj_x][adj_y] and not visited[adj_x][adj_y]:
visited[adj_x][adj_y] = 1
dq.append((adj_x, adj_y))
# make puzzle frag
r_all = [pos[0] for pos in locations]
c_all = [pos[1] for pos in locations]
r_min = min(r_all)
r_max = max(r_all)
c_min = min(c_all)
c_max = max(c_all)
r_len = r_max - r_min + 1
c_len = c_max - c_min + 1
frag = [[0]*c_len for _ in range(r_len)]
for r in range(r_len):
for c in range(c_len):
frag[r][c] += table[r+r_min][c+c_min]
return frag, len(locations)
def rotate(frag):
r_len = len(frag)
c_len = len(frag[0])
frag_new = [[0]*r_len for _ in range(c_len)]
for r in range(r_len):
for c in range(c_len):
frag_new[c][r_len-r-1] = frag[r][c]
return frag_new
# 퍼즐 조각이 딱 들어맞는지 확인
# 퍼즐을 보드의 찾아낸 여백 뭉탱이의 개수에 딱 맞는
# 것을 대상으로 is_match를 실행하는 것이기 때문에,
# 퍼즐이 빈 칸에 딱 들어맞는 경우는, 아까 보드에서 찾은
# 직사각형 형태에서 모든 값이 1이 되는 경우말고는 없음.
def is_match(x, y, puzzle, game_board):
for r in range(len(puzzle)):
for c in range(len(puzzle[0])):
if game_board[r+x][c+y] + puzzle[r][c] != 1:
return False
return True
def match_puzzle(r, c, frag_dict, visited_board, game_board):
# check empty sum
dq = deque([(r, c)])
cnt = 0
path = [(r, c)]
while dq:
now_x, now_y = dq.popleft()
cnt += 1
path.append((now_x, now_y))
for adj_x, adj_y in adj_pos(now_x, now_y):
if not(0 <= adj_x < len(game_board) and 0 <= adj_y < len(game_board[0])):
continue
if not game_board[adj_x][adj_y] and not visited_board[adj_x][adj_y]:
visited_board[adj_x][adj_y] = 1
dq.append((adj_x, adj_y))
# 빈 공간의 칸 개수 체크한 뒤,
# 그 칸 개수만큼에 해당하는 퍼즐 조각들을 대상으로
# 딱 들어맞는지 is_match로 체크
# game_board에서 탐색한 빈 칸 형태를 여백을 포함한 직사각형
# 형태로 생각해봤을 때, 그 때의 왼쪽 맨 위에서 시작하여(r_min, c_min)
# 퍼즐 조각(직사각형 형태)과 비교
puzzles = frag_dict[cnt]
r_min = min([pos[0] for pos in path])
c_min = min([pos[1] for pos in path])
for i in range(len(puzzles)):
puzzle = puzzles[i]
for _ in range(4):
puzzle = rotate(puzzle)
r_len = len(puzzle)
c_len = len(puzzle[0])
# 회전한 조각이 board 범위 안 넘어가는지 체크
if not(0 <= r_min + r_len - 1 < len(game_board) and 0 <= c_min + c_len - 1 < len(game_board[0])):
continue
if is_match(r_min, c_min, puzzle, game_board):
del frag_dict[cnt][i] # 사용한 조각 제거
return cnt
return 0
def solution(game_board, table):
answer = 0
# 퍼즐 조각 모두 찾기
visited = [[0]*len(table) for _ in range(len(table[0]))]
frag_dict = defaultdict(list)
for r in range(len(table)):
for c in range(len(table[0])):
if table[r][c] and not visited[r][c]:
frag, frag_sum = make_puzzle_frag_and_sum(r, c, table, visited)
frag_dict[frag_sum].append(frag)
# 보드에 조각 끼워넣기
visited_board = [[0]*len(game_board) for _ in range(len(game_board[0]))]
for r in range(len(game_board)):
for c in range(len(game_board[0])):
if not game_board[r][c] and not visited_board[r][c]:
visited_board[r][c] = 1
answer += match_puzzle(r, c, frag_dict, visited_board, game_board)
return answer풀이 요약
-
문제를 푸는 로직 자체는 생각해내기도 쉽고 간단하지만, 그걸 구현하는게 굉장히 복잡하고 어렵다.
로직은 뻔하다. 퍼즐 조각을 BFS로 찾고, 보드에서 BFS를 돌면서, 찾는 여백 뭉탱이마다 아까 구해둔 퍼즐 조각을 비교하여 딱 들어맞는걸 매칭시켜나가는 것이다.
그런데 그 구현이 복잡하니, 이해를 돕기 위해 구현 과정에서의 생각의 흐름에 따라 풀이를 정리해봤다.
1)
우선 퍼즐 조각을 정의해보자. > 테이블에서 BFS를 돌며 퍼즐 조각을 찾아야겠다. > 그런데 퍼즐 조각을 어떤 형태로 저장해놔야 board에서 매치를 시킬 수 있을까? 심지어 회전도 고려해야한다.. > 퍼즐을 직사각형 형태로 저장하면 되겠다. 보드에서의 빈 칸 뭉탱이를 마찬가지로 직사각형으로 표현해주면 퍼즐과 매칭해서 비교하기가 용이하다.make_puzzle_frag_and_sum 함수이다.
BFS를 돌면서 퍼즐 조각 구성 칸의 모든 좌표들을 구한다.
그리고 퍼즐 조각을 여백을 포함한 직사각형 형태로 저장하기 위해(아래 그림처럼)
뭉탱이 좌표 모음 locations에서 최소, 최대 행/열 값을 찾아서 직사각형의 가로, 세로 길이를 구한다.
그 크기 만큼의 직사각형 frag를 만들고, frag에 locations에 매칭되는 위치에 1을 채워넣는다.
이 후 퍼즐 조각과 조각의 칸 개수 합을 반환한다.
2)
보드의 빈 칸 뭉탱이마다 모든 퍼즐 조각을 다 비교하기엔 비효율적이다. 그러니 빈 칸 뭉탱이의 칸 개수와 같은 칸 개수인 퍼즐 조각만을 비교해주기 위해, 퍼즐 조각을 딕셔너리에 'key: 칸 개수, value: 직사각형 형태 퍼즐 조각 리스트' 형태로 담아주자.
3)
보드를 BFS로 돌면서, 미방문 상태이고 값이 0인 칸을 방문하면 거기서 BFS를 돌아서 빈 칸 뭉탱이를 쭉 구하자.
4)
이제 이 빈 칸 뭉탱이를 구할 때마다, 이 뭉탱이에 퍼즐 조각을 매칭시켜보자.
5)
딕셔너리에서 칸 개수가 뭉탱이와 똑같은 퍼즐 조각을 인덱싱하고, 그 퍼즐 조각들을 하나하나씩 각각 4번씩 rotate하면서 뭉탱이에 딱 들어맞는지 비교하면 되겠다.r_min, c_min을 구해서 직사각형의 맨 처음 칸부터 쭉 칸 비교하기
6)
직사각형의 뭉탱이에서 값이 0인 칸과 값이 1인 칸의 개수는, 퍼즐 조각의 값이 1인 칸과 값이 0인 칸의 개수와 같다. 퍼즐 조각을 고를 때 이미 뭉탱이의 값이 0인 칸의 개수가 퍼즐 조각의 값이 1인 칸의 개수와 같은 조각만을 인덱싱해줬으니까.
7)
그러면, 퍼즐 조각이 뭉탱이에 완전히 매칭된다는 것은 곧 직사각형 뭉탱이의 모든 빈 칸이 1로 채워져, 직사각형의 모든 값이 1이 됨을 의미한다. 즉, 뭉탱이와 직사각형을 한 칸씩 for로 비교하며 둘의 값을 더하고, 그 것이 1이 아닌 칸이 하나라도 존재하게 되면 매치가 안된다는 것을 의미한다. 이걸 이용해서 매치 여부를 판단하고, 매치한다면 퍼즐 조각의 칸 개수를 answer에 더 해주자.
8)
보드를 쭉 다 돌면서 모두 퍼즐 매칭을 실행했으면 answer을 출력해주자.
배운 점, 어려웠던 점
-
이때까지 풀어본 문제 중에 가장 구현이 복잡한 문제였다.
이런 문제는 생소한데, 만약 실제 코딩 테스트에서 이런 문제를 맞닥뜨리면 시간도 많이 잡아먹고, 설계한 로직대로 안됐을 때 멘탈 관리가 잘 안될 것 같다.. 이런 문제를 많이 풀어보고 구현 스킬도 좀 능숙해질 필요가 있음을 실감했다ㅠ
