[탐색] 퍼즐 조각 채우기 (파이썬)

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/84021

프로그래머스

문제 풀이

• 문제를 읽어보면 table에 있는 퍼즐 조각을 하나하나 옮겨보고 gb( game_board) 빈 공간에 딱 들어 맞는지 알아보는 문제 같다.
• 나 같은 경우는 gb에서 0으로 쭉 이어진 조각들을 구한 뒤 table을 탐색하면서 해당 조각이 table과 딱 들어맞는지 계산 함.(회전 포함)
  • gb에서 0으로 쭉 이어진 각 조각들을 구해서 peace 라는 리스트에 담아줌( 이 때 각 조각들의 좌표는 real 좌표가 아닌 시작점으로부터 떨어진 거리만큼의 좌표이므로 각 x,y 좌표에 i,j를 빼줌 ) 
  • eg.실제 (2,2),(2,3) 으로 이뤄진 조각은 peace에 담길 때는 (0,0),(0,1)이 담김
• 이 때, 시간을 조금이라도 줄여보기 위해 table도 미리 한번 탐색하면서 1로 이루어진 조각은 몇 개의 칸을 차지하는지, 그리고 gb에서 구한 peace에 담긴 좌표들에 탐색 시작 점 i,j를 각각 더해줬을때 번호가 같은지만 체크 해줄 용도로 table 각 조각들에 번호를 지정해줌
  • num 이라는 그래프를 만들어서 각 좌표에는 table 그래프에서 0으로 이뤄진 각 조각들의 몇 개로 이뤄졌는지 개수와 고유 넘버를 부여해줌
• 이제 peace에 담긴 각 조각(도형) 들로 table을 탐색 
• table의 0,0 부터 시작해서 해당 좌표[i,j]에 담긴 num좌표의 [0] 값과 각 도형의 길이가 같다면 딱 들어맞을 확률 있으므로 탐색 시작
• 이 때, num[1]에는 그 도형의 고유 번호를 담았으므로 peace 도형의 각 좌표에 [i,j]를 더해준 뒤 그 좌표가 모두 num[1]과 같은지 체크 하면 됨.
  • False 일 경우 시계 방향으로 rotation 할 것이므로 x,y = y, - x 가 된다.
• 도형에 딱 들어맞으면 answer 에는 도형 크기를 더해주고, complete 이라는 리스트를 만들어서 table의 해당 도형은 클리어 한 것이므로 고유 번호를 담아줘서 중복 탐색 막아줌. 
• gb의 도형인 peace도 딱 들어맞아서 더이상 탐색 할 필요 없으므로 break 조건을 걸어준다

소스 코드

 

from collections import deque
from copy import deepcopy

# x,y = -1,2
# nx = y
# ny = -x  시계 방향으로 90도 회전 시 각 좌표의 변화
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def find_peace(gb):	#게임 보드에서 0으로 이뤄진 각 도형들의 좌표 모음을 찾아서 리턴
    n = len(gb)
    peace = []
    for i in range(n):
        for j in range(n):
            if gb[i][j]==0:
                q = deque()
                q.append((i,j))
                temp = [[0,0]]
                gb[i][j]=1
                while(q):
                    x,y = q.popleft()
                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        if nx<0 or nx>=n or ny<0 or ny>=n:
                            continue
                        if gb[nx][ny]==0:
                            gb[nx][ny]=1
                            temp.append([nx-i,ny-j])
                            q.append((nx,ny))
                peace.append(temp)
    return peace

def solution(gb, table):
    answer = 0
    peace= find_peace(gb)
    n = len(gb)
    num = [[[0,0] for j in range(n)] for i in range(n)]
    temp = deepcopy(table)
    temp_num=1	# num이라는 그래프에 [도형 크기, 고유 번호] 를 입력하기 위한 과정
    for i in range(n):
        for j in range(n):
            if temp[i][j]==1:
                temp[i][j]=0
                m=1
                t = [[i,j]]
                q= deque()
                q.append((i,j))
                while(q):
                    x,y = q.popleft()
                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        if 0<=nx<n and 0<=ny<n and temp[nx][ny]==1:
                            m+=1
                            t.append([nx,ny])
                            temp[nx][ny]=0
                            q.append((nx,ny))
                for x,y in t:
                    num[x][y]=[m,temp_num]
                temp_num+=1

    complete = []
    for p in peace:	# 게임보드의 각 조각 탐색
        m = len(p)
        asd = False
        for i in range(n):
            if asd:
                continue                
            for j in range(n):
                if asd:
                    continue                
                if num[i][j][1] in complete:
                    continue
                if num[i][j][0]!=m:
                    continue
                NUM_T = num[i][j][1]
                pea = deepcopy(p)
                rot=0
                while(rot<=3):
                    tri = True
                    for x,y in pea:
                        nx = x + i
                        ny = y + j
                        if nx<0 or nx>=n or ny<0 or ny>=n or num[nx][ny][1]!=NUM_T:
                            tri = False
                            break
                    if tri:
                        complete.append(NUM_T)
                        asd=True
                        answer+=m
                        break
                    else:
                        rot+=1
                        for ri in range(m):
                            pea[ri][0],pea[ri][1] = pea[ri][1],-pea[ri][0]
        
    return answer

print(solution(
    [[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]]	
,[[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]]
))