[프로그래머스 위클리 챌린지 (lv3)] 3주차_퍼즐 조각 채우기 (DFS)

34번째로 풀이 ㅠㅠ

프로그래머스 위클리 챌린지 3주차 문제입니다.

34등 했네요..! 처음 풀어보는 3단계 수준의 문제였는데 시간은 오래 걸렸지만 그래도 한층 성장한 기분입니다.

(오랜만에 느껴보는 성취감)

---

3단계 수준인 것 같다

 

문제 설명

테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다.

• 조각은 한 번에 하나씩 채워 넣습니다.
• 조각을 회전시킬 수 있습니다.
• 조각을 뒤집을 수는 없습니다.
• 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.

다음은 퍼즐 조각을 채우는 예시입니다.

위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 나타냅니다. 모든 퍼즐 조각은 격자 칸에 딱 맞게 놓여있으며, 격자 칸을 벗어나거나, 걸쳐 있는 등 잘못 놓인 경우는 없습니다.

이때, 아래 그림과 같이 3,4,5번 조각을 격자 칸에 놓으면 규칙에 어긋나므로 불가능한 경우입니다.

• 3번 조각을 놓고 4번 조각을 놓기 전에 위쪽으로 인접한 칸에 빈칸이 생깁니다.
• 5번 조각의 양 옆으로 인접한 칸에 빈칸이 생깁니다.

다음은 규칙에 맞게 최대한 많은 조각을 게임 보드에 채워 넣은 모습입니다.

최대한 많은 조각을 채워 넣으면 총 14칸을 채울 수 있습니다.

현재 게임 보드의 상태 game_board, 테이블 위에 놓인 퍼즐 조각의 상태 table이 매개변수로 주어집니다. 규칙에 맞게 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 3 ≤ game_board의 행 길이 ≤ 50
• game_board의 각 열 길이 = game_board의 행 길이
  • 즉, 게임 보드는 정사각 격자 모양입니다.
  • game_board의 모든 원소는 0 또는 1입니다.
  • 0은 빈칸, 1은 이미 채워진 칸을 나타냅니다.
  • 퍼즐 조각이 놓일 빈칸은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
• table의 행 길이 = game_board의 행 길이
• table의 각 열 길이 = table의 행 길이
  • 즉, 테이블은 game_board와 같은 크기의 정사각 격자 모양입니다.
  • table의 모든 원소는 0 또는 1입니다.
  • 0은 빈칸, 1은 조각이 놓인 칸을 나타냅니다.
  • 퍼즐 조각은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
• game_board에는 반드시 하나 이상의 빈칸이 있습니다.
• table에는 반드시 하나 이상의 블록이 놓여 있습니다.

입출력 예

입출력 예

입출력 예 설명

입출력 예 #1

입력은 다음과 같은 형태이며, 문제의 예시와 같습니다.

입출력 예 #2

블록의 회전은 가능하지만, 뒤집을 수는 없습니다.

---

나의 풀이

문제 이해

잘못된 경우

이렇게 하나의 빈 칸에 블록 2개가 들어가면 안되고

맞는 경우

빈 칸 하나당 하나의 블록만 들어가야 한다. 즉, 빈 칸과 블록의 모양이 동일해야 한다.

 

아이디어

이 문제에서는 DFS 알고리즘을 사용했다. (BFS 알고리즘을 사용해도 된다)

DFS 관련 설명

2021.06.26 - 깊이 우선 탐색(DFS, Depth First Search) 파이썬 구현

깊이 우선 탐색(DFS, Depth First Search) 파이썬 구현

 

BFS 관련 설명

2021.05.23 - 너비 우선 탐색(BFS, Breadth First Search) 파이썬 구현

너비 우선 탐색(BFS, Breadth First Search) 파이썬 구현

 

전체적인 풀이 과정

• table에서 블록들을 구한다. (shapes에 저장)
• game_board에서 빈 칸들을 구한다. (spaces에 저장)
• spaces와 shapes에 있는 블록(혹은 빈 칸) 들을 적당히 회전해서 일치하는 블록이 있다면
  • 블록의 크기 만큼 answer에 더하고,
  • shapes에서 제거한다.

 

좀 더 자세하게

• table 및 game_board에서 블록 및 빈 칸 구하기
  • DFS 알고리즘 사용 (깊이 우선 탐색)
    • table에서 1로 표시된 것이 블록일 때
    • 1을 찾아서 그 주변(상 하 좌 우)에 1이 또 있나 확인
    • 있다면 거기로 이동
    • 더 이상 주변(상 하 좌 우)에 1이 없을 때까지 반복
    • 찾은 블록들은 shapes (리스트)에 저장
    • 찾은 빈 칸들은 spaces (리스트)에 저장
  • 위치 재정렬
    • 찾은 블록(및 빈 칸)들은 그 좌표 값이 저장된다.
    • 모양에 대한 정보가 필요한 것이므로 같은 모양일 때 같은 값을 가져야 한다.
    • 그렇기 때문에 가장 왼쪽, 위로 밀어낸다. (0, 0)부터 시작하도록
    • 또한 어떤 블록이 4칸짜리 블록이라면 4개의 (x, y) 좌표 값을 가지고 있다.
      • 각 칸마다 좌표 값을 갖고 있기 때문.
      • 그래서 각 칸 정보들의 순서가 항상 일정하지 않다. (그래도 같은 모양이다)
    • 같은 모양일 때 같은 값을 가져야 하므로 정렬하여 반환한다
    • game_board의 빈 칸도 동일하게 처리
• 블록 회전
  • 같은 블록이더라도 회전하면 최대 4개의 다른 모양이 나올 수 있다. ( ㅏ ㅜ ㅓ ㅗ )
  • 매번 회전시키며 비교하기엔 비효율적이고, 가독성이 떨어진다.
  • 그래서 동일한 모양일 때 항상 동일한 값이 나오도록 한다.
  • 예를 들어
    • 'ㅏ' 모양이 들어가도 'ㅗ'가 나오고, 'ㅜ' 모양이 들어가도 'ㅗ'가 나오도록 회전시킨다.
  • 블록을 시계 방향으로 4회 회전시킨다.
  • 각 결과를 리스트에 담는다.
  • 특정한 기준에 따라 일정한 값이 나오도록 한다.
    • 기준에는 최소값, 최대값, 정렬 등을 사용할 수 있다.
    • 정렬을 하는 경우는 최소값이나 최대값을 구하는 것보다 더 많은 비용과 시간이 발생하므로
    • 최소값이나 최대값을 사용한다.
  • 시계 방향으로 회전 방법
    1. 블록을 이루는 각 칸의 x, y 좌표를 서로 맞바꾼다. (전치)
    2. 가로의 길이 width를 구한다.
    3. 전치된 모든 칸의 x 값을 width 에서 뺀다. (width - x좌표 값)
    4. rearrange() 함수를 사용해 위치를 재정렬 한다.
• 일치하는 값 구하기
  • answer = 0으로 초기화 (answer은 일치하는 블록의 개수를 의미)
  • 빈 칸들을 순회한다.
    • 각 빈 칸에서 블록들을 순회하며 일치하는 블록을 찾는다
    • 일치하는 블록이 등장했다면
      • 블록의 개수만큼 answer에 더한다
      • 블록의 목록에서 일치한 블록을 제거한다.
  • 구해진 answer이 이 문제의 정답이 된다.

 

전체 소스코드

def dfs(table, i, j, shape, find = 1):
        # 우 좌 하 상
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0] 
    stack = [[i, j]] # 현재 위치 스택에 저장
    shape.append((i, j))
    
    while stack:
        a, b = stack.pop()
        table[a][b] = -1 # 방문 처리
        for i in range(4): # 우 좌 하 상 순으로 스택에 저장 -> 상 하 좌 우 순으로 꺼내져 수행된다.
            x = a + dx[i]
            y = b + dy[i]
            if 0 <= x < len(table) and 0 <= y < len(table[0]) and table[x][y] == find:
                table[x][y] = -1
                stack.append([x, y])
                shape.append((x, y))
                
# 블록이나 빈 칸을 (0, 0)을 시작점으로 옮김
def rearrange(shape):
    minX = min([x[1] for x in shape])
    minY = min([x[0] for x in shape])
    shape = [(s[0]-minY, s[1]-minX) for s in shape]
    return sorted(shape) # 블록이 여러 칸으로 이루어진 경우 같은 모양에서 같은 결과를 위해 정렬해서 반환

# 여러 방향으로 회전 후 하나의 값 반환
def rotate(shape):
    if len(shape) == 1: return shape
    shapes = []
    shape = list(shape)
    shape.sort()
    width = max([x[1] for x in shape]) - min([x[1] for x in shape])
    height = max([x[0] for x in shape]) - min([x[0] for x in shape])
    # 시계 방향으로 4회 회전
    for _ in range(4):
        tmp = []
        # 시계 방향으로 회전하는 방법
        # 1. (x, y) 값을 (y, x)로 x, y를 맞바꾸는 '전치'
        for pos in shape:
            tmp.append((pos[1], pos[0])) # 전치
        # 2. 전치된 결과에서 x 좌표를 가로 길이에서 뺀다.
        tmp = [(x[0], width - x[1]) for x in tmp]
        tmp = rearrange(tmp) # 재정렬
        shape = tmp # 시계 방향으로 회전 한 블록을 shape에 다시 저장
        shapes.append(shape)
        width, height = height, width # 2x3 크기의 블록이 회전하면 3x2가 되므로 width, height를 맞바꾼다.
    
    # 4번 회전한 결과가 담긴 shapes의 최소값을 반환하면 
    # 같은 구성의 순서가 다른 리스트에서도 항상 동일한 결과 반환
    return min(shapes) 
                
def solution(game_board, table):
    # table에서 추출된 블록들과 game_board에서 추출된 빈 칸들을 저장하는 리스트
    shapes, spaces = list(), list() 
    # game_board와 table의 크기가 같다고 주어졌기 때문에 한 번에 돌릴 수 있음
    for i in range(len(table[0])):
        for j in range(len(table)):
            # table에서 블록 추출하는 dfs
            if table[i][j] == 1: # 1이면 블록
                shape = list()
                dfs(table, i, j, shape) # table에서 블록(1) 추출
                shape = rearrange(shape) # 추출한 블록 (0, 0) 부터 시작하도록 위치 값 조정
                shape = rotate(shape) # 회전 후 항상 동일한 결과 반환
                shapes.append(shape) # shapes 에서 블록들 관리
            # game_board에서 빈 칸 추출하는 dfs
            if game_board[i][j] == 0: # 0이면 빈 칸
                space = list()
                dfs(game_board, i, j, space, find = 0) # game_board에서 빈 칸(0) 추출
                space = rearrange(space) # 추출한 공백 (0, 0) 부터 시작하도록 위치 값 조정
                space = rotate(space) # 회전 후 항상 동일한 결과 반환
                spaces.append(space) # spaces 에서 공백들 관리
                
    answer = 0
    for space in spaces:
        for shape in shapes:
            if space == shape: # 같은 모양이 있다면
                answer += len(shape) # 블록의 개수만큼 더한다
                shapes.remove(shape) # 사용된 블록은 제거
                break
    return answer

테스트 결과