99클럽 코테 스터디 4일차 TIL

[level 3] 퍼즐 조각 채우기 - 84021

문제 링크

성능 요약

메모리: 10.3 MB, 시간: 0.53 ms

구분

코딩테스트 연습 > 깊이／너비 우선 탐색（DFS／BFS）

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2024년 04월 16일 23:11:26

문제 설명

테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 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에는 반드시 하나 이상의 블록이 놓여 있습니다.

---

입출력 예

game_board	table	result
[[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]]	14
[[0,0,0],[1,1,0],[1,1,1]]	[[1,1,1],[1,0,0],[0,0,0]]	0

---

입출력 예 설명

입출력 예 #1

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

입출력 예 #2

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

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

 

 

풀이

from copy import deepcopy

# 상하좌우 이동을 위한 배열
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 깊이 우선 탐색(DFS)를 이용해 그래프에서 연결된 영역을 탐색하는 함수
def dfs(x, y, graph, position, n, num) :
    res = [position]

    # 현재 위치에서 상하좌우로 이동
    for k in range(4) :
        nx, ny = x + dx[k], y + dy[k]

        # 이동한 위치가 그래프 내에 있고, 탐색하려는 숫자(num)와 일치하면
        if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] == num :
            graph[nx][ny] = 2  # 방문 표시
            # 재귀적으로 다음 위치 탐색
            res = res + dfs(nx, ny, graph, [position[0] + dx[k], position[1] + dy[k]], n, num)

    return res

# 퍼즐 조각을 90도 회전시키는 함수
def rotate(lst) :
    n = len(lst)

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

    for i in range(n) :
        for j in range(n) :
            rotate_lst[j][n-1-i] = lst[i][j]

    return rotate_lst

# 주 함수
def solution(game_board, table) :
    answer = 0
    n = len(game_board)
    game_board_copy = deepcopy(game_board)
    block = []

    # 게임 보드에서 빈 공간을 찾아 해당 공간의 형태를 추출
    for i in range(n) :
        for j in range(n) :
            if game_board_copy[i][j] == 0 :
                game_board_copy[i][j] = 2  # 방문 표시
                result = dfs(i, j, game_board_copy, [0,0], n, 0)[1:]
                block.append(result)

    # 테이블 위의 퍼즐 조각을 90도씩 회전시키며 맞춰보기
    for r in range(4) :
        table = rotate(table)
        table_rotate_copy = deepcopy(table)

        # 회전된 테이블에서 퍼즐 조각의 형태를 추출
        for i in range(n) :
            for j in range(n) :
                if table_rotate_copy[i][j] == 1 :
                    table_rotate_copy[i][j] = 2  # 방문 표시
                    result = dfs(i, j, table_rotate_copy, [0,0], n, 1)[1:]
                    # 추출된 퍼즐 조각이 게임 보드의 빈 공간과 일치하면
                    if result in block :
                        block.pop(block.index(result))  # 일치하는 블록 제거
                        answer += len(result) + 1  # 채워진 칸 수 증가
                        table = deepcopy(table_rotate_copy)  # 테이블 업데이트
                    else :
                        table_rotate_copy = deepcopy(table)  # 일치하지 않으면 원래 상태로 복구

    return answer

• 이번에 풀이는 구현 부분에서 많은 애를 먹었다. 접근 방식을 탐색, 회전, 구현 부분으로 나누어서 진행을 해야 그나마 수월하게 할 수 있었을 것이라고 생각한다. 
• 이번에도 역시 혼자서 구현하지 못하였다. BFS로 먼저 풀이를 진행하였으나, 어디서 구현이 잘못된것인지 케이스 11에서 시간 초과가 발생하여서 다른 분의 풀이를 참고하였다.
• 이 문제 해결 방식은 브루트 포스와 백트래킹 기법을 결합한 것으로 볼 수 있다. 각각의 빈 공간에 대해 모든 가능한 퍼즐 조각과 그 회전 상태를 시도해보며, 가능한 해결책을 찾아낸다. 

1. 게임 보드에서 빈 공간 탐색
   • 게임 보드의 각 칸을 순회하면서 빈 공간 (0으로 표시된 곳)을 찾습니다
   • 빈 공간을 찾으면, 그 위치에서 깊이 우선 탐색(DFS)를 시작하여 연결된 모든 빈 칸을 찾아내며, 이들의 상대적 위치를 저장합니다. 이때, graph[nx][ny] = 2를 통해 이미 방문한 칸을 표시하여 중복 탐색을 방지합니다.
   • 각 빈 공간에 대해 얻은 삭대적 위치 정보를 block 리스트에 저장합니다. 이 리스트는 나중에 테이블 위의 퍼즐 조각을 비교하는데 사용됩니다.
2. 테이블 위의 퍼즐 조각 탐색 및 매칭
   
   • 테이블 위츼 퍼즐 조각들 역시 게임 보드의 빈 공간을 탐색할 때와 유사한 방법으로 탐색합니다. 다만 여기서는 퍼즐 조각이 있는 곳(1로 표시된 곳)을 찾아내야 합니다.
   • 각 퍼즐 조각에 대해, 그 조각을 0도, 90도, 180도, 270도로 회전시키면서 게임 보드의 빈 공간과 일치하는지 확인합니다. 이를 위해 rotate함수를 사용하여 퍼즐 조각을 회전시키고, dfs를 사용하여 퍼즐 조각의 상대적 위치를 구합니다.
   • 회전시킨 퍼즐 조각이 게임 보드의 어떤 빈 공간과도 일치한다면, 그 퍼즐 조각은 게임 보드에 맞춰진 것으로 간주하고, 해당 빈 공간 정보를 block 리스트에서 제거합니다. 동시에, answer 변수에 퍼즐 조각이 차지하는 칸의 수를 더해줍니다.