99클럽 코테 스터디
스터디가 아닌 날에 푸는 건 처음이다. 난이도는 무난하지만 구현할 것이 많아 시간은 꽤 걸렸고, 굉장히 실제 코테와 비슷한 유형이었다. 좋은 연습이 되었다.
1번 문제 퍼즐 조각 채우기 : https://school.programmers.co.kr/learn/courses/30/lessons/84021
출처 : 프로그래머스
1번 문제 퍼즐 조각 채우기
풀이 접근
정석적인 dfs+구현 문제이다.
퍼즐의 모양을 '정확하게' 저장해야 함이 관건이다. 이 정확함을 보장하기 위해, dfs의 시작은 반드시 조각의 맨 위 맨 왼쪽(책 읽는 순서대로 첫 칸)이 되도록 하고, dfs로 움직일 때마다 상하좌우+되돌아가기의 5방향을 퍼즐의 고유 정보로 저장했다. 움직인 순서를 기록해서 리스트 같은 걸로 만들어도 좋겠지만, 좀 더 효율성을 증대하기 위해 가상의 6진법 고유번호를 도입했다.
퍼즐 조각은 뒤집지 못하되 회전시킬 수 있으므로, 90도씩 돌려가면서 각 조각이 회전한 형태의 고유번호도 같은 번호에 저장하도록 했다 (이 때에도 회전된 조각의 맨 위 맨 왼쪽 칸에서부터 시작하도록 주의한다.)
고유번호를 6진법으로 나타내고 앞에서부터 읽으면 (오른쪽1 아래2 왼쪽3 위4 돌아갈땐5)의 모양이 된다.
예컨대 107이라는 번호가 있으면 이는 6진법으로 255이고, 이는 아래-돌아가기-돌아가기(종료)를 의미한다. 즉 세로로 두칸짜리 조각이라는 의미이고, 아래 그림(실제 문제의 예시 테스트케이스이다)의 하늘색 조각(5번)의 번호가 된다. 게임보드에서 맨 오른쪽 위 세로 두칸짜리 빈 칸도 107이 나올 것이고, 이는 두 조각의 모양이 완전히 일치함을 나타낸다. 물론 초록색 조각(4번)의 90도 or 270도 회전 버전의 번호도 107이다.
주) 다풀고 생각해보니 0까지 껴서 5진법으로 해도 된다. 뭐하러 6진법했지?
코드 (Python3, 통과, 최대 18.95ms, 10.6MB)
dfs(x,y,p)로 p번째 조각을 싹 훑고 나면 해당 조각이 차지하고 있던 칸의 번호는 0과 1이 아닌 -p가 된다. 이를 통해 90도씩 회전시킨 퍼즐조각 판에서도 퍼즐조각의 번호를 똑같이 맞출 수 있다. (특정 조각을 소모하면 해당 조각을 회전시킨 모양도 더 쓸 수 없으므로 번호를 똑같이 맞출 필요가 있다.)
pieces[p]는 p+1번 조각의 고유번호이다. 위에 있는 그림의 예시의 번호와는 달리, 책 읽는 순서대로 읽으므로, 하늘색 2칸짜리 조각이 1번, 노란색 5칸짜리가 2번, 보라색 네칸짜리가 3번, 빨간색 3칸짜리가 4번, 초록색 2칸짜리가 5번이다.
테이블을 90도, 180도, 270도 회전시킨 모양에 대해서도 dfs를 똑같이 돌려준다. table을 회전시키고 뒤에 _90, _180, _270을 붙이고, dfs도 똑같이 붙이고, pieces에도 똑같이 붙였다.
마지막에 게임보드의 구멍들과 보유한 퍼즐조각의 모양을 일치 비교할 때, 어떤 조각을 소모했는 지 표시하면서 동시에 몇 칸을 채웠는지 알기 위해 placed[p]는 p+1번 조각을 아직 소모 안했으면 0, 소모했으면 해당 조각의 사이즈를 표시해두고, 모든 구멍에 모든 조각(이미 소모한 건 안해도 됨)을 일치비교한 후 placed의 총합(=채운 칸 개수)을 answer로 리턴하면 된다.
def solution(game_board, table):
# 90도씩 회전시킨 조각을 다 만들기 위함, dfs할거니까 처음부터 바깥탈출안되게 벽발라놓기
n = len(table)
table.append([0]*(n+1))
game_board.append([1]*(n+1))
table_90 = [[0]*(n+1) for _ in range(n+1)]
table_180 = [[0]*(n+1) for _ in range(n+1)]
table_270 = [[0]*(n+1) for _ in range(n+1)]
for i in range(n):
table[i].append(0)
game_board[i].append(1)
for j in range(n):
table_90[j][n-1-i] = table[i][j]
table_180[n-1-i][n-1-j] = table[i][j]
table_270[n-j-1][i] = table[i][j]
# 오른쪽1 아래2 왼쪽3 위4 돌아갈땐5 6진법으로 조각의 정보를 저장
def dfs(x,y,p):
table[x][y] = -p # 회전시켰을때도 알아보기 위해 0으로 만드는게아니라 조각 번호의 음수로 바꿈
size[p-1] += 1 # 조각의 사이즈 저장
for i in range(4):
dx,dy = directions[i]
if table[x+dx][y+dy]>0:
pieces[p-1] *= 6
pieces[p-1] += i+1
dfs(x+dx,y+dy,p)
pieces[p-1] *= 6
pieces[p-1] += 5
return
def dfs_90(x,y,p):
table_90[x][y] = 0
for i in range(4):
dx,dy = directions[i]
if table_90[x+dx][y+dy]>0:
pieces_90[p-1] *= 6
pieces_90[p-1] += i+1
dfs_90(x+dx,y+dy,p)
pieces_90[p-1] *= 6
pieces_90[p-1] += 5
return
def dfs_180(x,y,p):
table_180[x][y] = 0
for i in range(4):
dx,dy = directions[i]
if table_180[x+dx][y+dy]>0:
pieces_180[p-1] *= 6
pieces_180[p-1] += i+1
dfs_180(x+dx,y+dy,p)
pieces_180[p-1] *= 6
pieces_180[p-1] += 5
return
def dfs_270(x,y,p):
table_270[x][y] = 0
for i in range(4):
dx,dy = directions[i]
if table_270[x+dx][y+dy]>0:
pieces_270[p-1] *= 6
pieces_270[p-1] += i+1
dfs_270(x+dx,y+dy,p)
pieces_270[p-1] *= 6
pieces_270[p-1] += 5
return
# 게임보드는 1이 아닌 0(구멍)을 기준으로 dfs해서 구멍 모양을 기록
def dfs_board(x,y,p):
game_board[x][y] = 1
for i in range(4):
dx,dy = directions[i]
if not game_board[x+dx][y+dy]:
holes[p-1] *= 6
holes[p-1] += i+1
dfs_board(x+dx,y+dy,p)
holes[p-1] *= 6
holes[p-1] += 5
return
pieces = []
size = []
directions = ((0,1),(1,0),(0,-1),(-1,0))
for i in range(n):
for j in range(n):
if table[i][j] > 0:
pieces.append(0)
size.append(0)
dfs(i,j,len(pieces))
pieces_90 = [0]*len(pieces)
pieces_180 = [0]*len(pieces)
pieces_270 = [0]*len(pieces)
for i in range(n):
for j in range(n):
if table_90[i][j]:
dfs_90(i,j,-table[n-1-j][i])
if table_180[i][j]:
dfs_180(i,j,-table[n-1-i][n-1-j])
if table_270[i][j]:
dfs_270(i,j,-table[j][n-1-i])
placed = [0]*len(pieces) # 게임보드에 이미 놓은 조각은 1로 표시
holes = []
for i in range(n):
for j in range(n):
if not game_board[i][j]:
holes.append(0)
dfs_board(i,j,len(holes))
for hole in holes:
for i in range(len(pieces)):
if not placed[i]:
if pieces[i] == hole or pieces_90[i] == hole or pieces_180[i] == hole or pieces_270[i] == hole:
placed[i] = size[i]
break
answer = sum(placed)
return answer