[프로그래머스] 위클리 챌린지 3주차 퍼즐 조각 채우기 파이썬 풀이

※사용언어 : 파이썬 ※

 

▼ 문제 링크 ▼

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

코딩테스트 연습 - 3주차

 

 

---

 

 

문제 접근

문제가 상당히 복잡합니다. 접근 방식을 그림과 함께 설명할 예정이니 차근차근 집중하여 보는 것을 추천드립니다.

 

첫 번째로, game_board의 빈 공간 좌표와, table의 블록 좌표값을 BFS(DFS를 사용해도 된다)를 사용하여 찾아낸다. 이때 찾아낸 좌표값들을 정렬을 해줘야 한다. 정렬을 하는 이유는 추후에 설명하겠다.

 

두 번째로, game_board의 빈 공간 좌표와, table의 블록 좌표값을 기준점을 잡아 통일시켜줘야 한다. 해당 문장이 어떤 의미를 내포하는지 문제에 나온 예제 그림을 보며 설명하도록 하겠다.

game_board에 파란색으로 칠해진 영역에 table의 노란블록(2번 블록)이 들어갈 수 있다. 하지만 game_board의 파란 영역의 좌표와 table의 노란 블록(2번 블록)의 좌표값은 다르다.

두 영역의 좌표값

서로 다른 좌표값을 가진 두 영역(game_board의 파란영역, table의 노란 블록)이 같은 모양임을 알기 위해 기준점을 세워 해당 기준점을 기준으로 각 좌표를 변경해줘야 한다.

가령 game_board의 파란 영역을 예로 들면, game_board 파란영역의 좌표 중 좌표값이 최소 x값과 최소 y값인 [ 0, 2 ] 를 [ 0 , 0 ]으로 만들어 블록(영역)의 모든 좌표가 0 , 0에서부터 시작하도록 만든다. 그러기 위해서는 y좌표에서 -2를 해줘야 하기 때문에, 똑같이 다른 좌표에서도 y좌표값에 -2를 해준다. 

[ 0 , 3 ] , [ 1 , 3 ] , [ 2 , 3 ] , [ 2 , 4 ] ▶ [ 0-0 , 3-2 ] , [ 1-0 , 3-2 ] , [ 2-0 , 3-2 ] , [ 2-0 , 4-2 ]

연산을 통해 좌표값을 조정해준다. table도 똑같이 해당 작업을 거친다. 해당 작업을 거치면, 파란영역은 0,0을 기준으로 좌표값이 변경된다.

좌표값이 변경된 모습

여기서 정렬을 하는 이유를 우리는 알 수 있다.

만약, 지금 예시로 들고있는 table의 노란 블록과 game_board의 파란 영역은 0,0을 기준으로 좌표값을 변경하게 되면 같은 좌표값을 가지게 될 것이다. 하지만 이때, 좌표값이 정렬되지 않았다면 같은 좌표값을 가지지만, 각 좌표값의 위치가 일치하지 않는 경우가 생긴다. 예를 들어 game_board의 0,0 좌표의 인덱스 값은 0이지만, table의 0,0 좌표의 인덱스 값은 1인 경우, 같은 좌표이지만 인덱스 값이 달라 매칭이 되지 않는 상황이 생긴다. 이러한 상황을 방지하기 위해 정렬을 해준다.

 

세 번째로 회전이다. 

매칭이 되지 않는 경우, 블록을 회전해서 매칭이 되는지 안되는지 판단할 수 있다. 대표적인 예가 table의 3번 블록이다.

3번 블록은 현재 모양으로는 game_board의 보라색 영역에 들어갈 순 없지만, 회전을 한다면 해당 영역에 들어갈 수 있다.

game_board의 빈 공간 좌표와, table 블록 좌표를 검사하여 매칭 되지 않는 경우에는 table 블록을 회전시켜준다. 

간단한 예제와 함께 2차원 배열이 회전할 때 좌표값이 어떤 식으로 변경되는지 알아보자.

회전 이전에 0, 2 였던 값은  회전 이후 2 , 2 로 바뀌었다. 여기서 공식을 하나 도출해낼 수 있다. 바로 기존 y값이 회전 이후 x값이 되고 회전 이후 y값은 배열의 크기 - 1 - x값이 된다. 즉, 배열 [x][y] →회전→ [y][배열 크기 - 1 - x] 이 된다.

 

이제 마지막으로 문제의 조건을 하나 살펴봐야한다. 문제에 보면, '조각은 한 번에 한 번씩만 집어넣는다'라는 조건이 있기 때문에 game_board의 빈 영역에 조각을 넣게 되면 break를 통해 멈추고 다음 영역을 검사해야 한다.

 

 

---

 

 

문제풀이(With Python)

from collections import deque
import copy
global answer
answer=0


dx=[-1,1,0,0]
dy=[0,0,-1,1]
empty_g = [] #game_board의 빈 영역
block_t = [] #table 의 블록값


def bfs(x,y,N,visited,array,check):
    space=[]
    que=deque()
    que.append([x,y])
    space.append([x,y])
    visited[x][y] = True
    while que:
        px,py=que.popleft()
        for i in range(4):
            nx=px+dx[i]
            ny=py+dy[i]
            if nx<0 or ny<0 or nx>=N or ny>=N:
                continue
            if visited[nx][ny]==False and array[nx][ny]==check:
                visited[nx][ny]=True
                que.append([nx,ny])
                space.append([nx,ny])

    return sorted(space)


def rotate(b, N):
    new_board=[]
    for block in b:
        new_board.append([block[1],N-1-block[0]])
    return sorted(standard(new_board,N))

def standard(b,N):
    change=[]
    minx=N
    miny=N
    for i in b:
        minx=min(minx, i[0])
        miny=min(miny,i[1])
    for x,y in b:
        change.append([x-minx,y-miny])
    return sorted(change)

def solution(game_board, table):
    global answer
    N=len(game_board)

    visited_g = [[False for _ in range(N)] for _ in range(N)]
    visited_t = [[False for _ in range(N)] for _ in range(N)]

    for i in range(N):
        for j in range(N):
            if game_board[i][j]==0 and visited_g[i][j]==False:
                empty_g.append(bfs(i,j,N,visited_g,game_board,0))
            if table[i][j]==1 and visited_t[i][j]==False:
                block_t.append(bfs(i,j,N,visited_t,table,1))
            else:
                continue
	
    # 찾은 table 블록 좌표를 0,0 기준으로 변환
    table_block=[]
    for a in block_t:
        table_block.append(standard(a,N))
   
   # 찾은 game_board의 빈영역 좌표를 0,0 기준으로 변환
    game_block=[]
    for b in empty_g:
        game_block.append(standard(b,N))

    for g_block in game_block:
        if g_block in table_block: 
            answer+=len(g_block)
            table_block.remove(g_block)
        else:
            flag=False
            for t_block in table_block:
                temp = copy.copy(t_block)
                for z in range(4):
                    if g_block==temp:
                        answer+=len(g_block)
                        table_block.remove(t_block)
                        flag=True
                        break
                    temp=rotate(temp,N)
                if flag: 
                # 혹시라도 회전 후 다른 빈 영역에 조각이 들어갈 수 있기 때문에
                # 한 번에 조각을 넣을 수 있는 조건을 만족하기 위해 break를 넣어줌
                    break

    return answer