[프로그래머스Lv.3] 퍼즐조각 채우기(파이썬)

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

프로그래머스

 

bfs,dfs를 쓰는 거 까지는 캐치했지만

어떻게 활용할지 몰라서 구글링을 했습니다.

 

문제풀이 순서

 

1. table에 있는 블록의 좌표를 구한다

-->[0,0]을 기준으로 두고

블록의 좌표를 구하고 저장합니다.

 

2. 테이블을 90도로 돌려가면서 비교한다.

-->테이블 배열을 돌려가면서

bfs를 해주고

해당 좌표의 블록이 있는지 찾아봅니다.

찾고 있으면 해당 블록을 제거해줍니다.

 

세세한 풀이

 

DFS를 사용할 수 있지만

BFS가 직관적인 이해가 쉬워서 BFS를 사용했습니다.

 

1. table블록좌표 bfs

-->채워져있는 좌표만을 칠합니다.

이미 지나간 좌표는 2로 표기해두어

visited를 별도로 쓰지 않고 용량을 최소화했습니다.

table어디에 블록이 있든 간에

좌표는 [0,0]을 기준으로 찍혀서

[0,0],[1,0],[1,-1]이런식으로 보관됩니다.

 

2. board돌려주면서 bfs

-->우선 board를 90도로 돌려줍니다.

그 다음 비어있는 좌표를 기준으로 bfs를 해줍니다.

bfs를 하고 결과값은 block의 좌표처럼

[0,0]을 기준으로 나온 좌표들.

이게 블록에 있다면 해당 블록을 제거하고

정답에 길이만큼 더해줍니다.

만약에 없다면 해당 지점은 방문안한걸로 다시 되돌려줍니다.

 

실수했던 포인트

1과 2의 BFS조건이 다르다

-->1의 BFS는 '채워져있는 것'을 기준으로

2의 BFS는 '비워져있는 것'을 기준으로 탐색합니다.

글자 하나 차이로, 두 문제에서 써야하는 BFS함수를 따로 구현해줘야합니다.

처음에는 1의 BFS를 2에 그대로 썼다가

답이 제대로 나오지 않았는데

트레킹해보니 조건에서 저런 사소한 차이가 있어

아예 BFS함수를 2개 따로 만들었습니다.

 

from copy import deepcopy
from collections import deque

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def solution(game_board, table):
    n = len(game_board)
    answer = 0

    def bfs(board, x, y):
        board[x][y] = 2
        block = []
        block.append((0, 0))
        q = deque()
        q.append((x, y, 0, 0))

        while q:
            px, py, cx, cy = q.popleft()

            for d in range(4):
                nx = px + dx[d]
                ny = py + dy[d]
                ncx = cx + dx[d]
                ncy = cy + dy[d]

                if nx < 0 or nx >= n or ny < 0 or ny >= n:
                    continue

                if board[nx][ny] == 0 or board[nx][ny] == 2:
                    continue

                board[nx][ny] = 2
                q.append((nx, ny, ncx, ncy))
                block.append((ncx, ncy))

        return block

    # bfs 1 2로 나눈 이유-->
    # 1은 table블록좌표-->채워진 걸 기준으로 탐색
    # 2는 보드빈거 좌표-->비워진 걸 기준으로 탐색
    # 저거 하나 고치면 되긴하는데, 아예 코드 복붙하고 조건부만 바꾸는 게 좋겠다 생각
    def bfs2(board, x, y):
        board[x][y] = 2
        block = []
        block.append((0, 0))
        q = deque()
        q.append((x, y, 0, 0))

        while q:
            px, py, cx, cy = q.popleft()

            for d in range(4):
                nx = px + dx[d]
                ny = py + dy[d]
                ncx = cx + dx[d]
                ncy = cy + dy[d]

                if nx < 0 or nx >= n or ny < 0 or ny >= n:
                    continue

                if board[nx][ny] == 1 or board[nx][ny] == 2:
                    continue

                board[nx][ny] = 2
                q.append((nx, ny, ncx, ncy))
                block.append((ncx, ncy))

        return block

    def rotation(board):

        ro = [[0] * n for _ in range(n)]

        for i in range(n):
            for j in range(n):
                ro[j][n - 1 - i] = board[i][j]

        return ro

    # 1. table에 있는 블록들 좌표를 받아보자
    blocks = []
    for i in range(n):
        for j in range(n):
            if table[i][j] == 1:
                block = bfs(table, i, j)
                blocks.append(block)

    # 2 game_board를 돌려가면서 좌표랑 확인

    for d in range(4):
        rota = rotation(game_board)

        for i in range(n):
            for j in range(n):
                if rota[i][j] == 0:
                    now = bfs2(rota, i, j)
                    # block에 있다면 블록을 빼주고 블록수를 정답에 반영
                    if now in blocks:
                        answer += len(now)
                        blocks.remove(now)

                    # block에 없다면 다시 빈칸으로 되돌리기
                    else:
                        for x, y in now:
                            rota[x + i][y + j] = 0

        game_board = deepcopy(rota)

    return answer