-
프로그래머스) 퍼즐 조각 채우기 (lv.3)알고리즘/프로그래머스 2022. 8. 21. 14:32
https://school.programmers.co.kr/learn/courses/30/lessons/84021?language=python3
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
탐색을 통해서 도형의 모양을 찾고 보드에 넣을 수 있는 도형의 크기의 합을 구하는 문제이다.
먼저, 보드를 돌면서 맞춰야 하는 퍼즐의 모양을 dfs를 통해 탐색하였다. 여기서 position은 가장 기준의 되는 부분을 (0, 0)으로 잡고 상하좌우 네 방향으로 돌면서 기준점에서 이동하는 방향을 통해 block을 구한다.
보드 안에있는 모든 구멍을 다 구해서 blocks 배열에 넣었으면 이제 테이블을 돌면서 퍼즐 모양을 같은 dfs 방식을 통해서 구한다. 만약 퍼즐이 blocks 배열 안에 있어 보드의 구멍에 맞는다면 도형이 사용되었음(방문표시)을 뜻하는 2를 이용해 퍼즐보드를 채워주고 아니라면 퍼즐보드를 90도 방향으로 회전시켜 다시 퍼즐 모양을 찾아 보드에 맞는 퍼즐을 찾는다.
import copy def solution(game_board, table): def dfs(graph, x, y, position, n, num) : directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] result = [position] for i, j in directions: nx, ny = x+i, y+j if 0<= nx <n and 0<=ny<n and graph[nx][ny] == num : graph[nx][ny] = 2 result += dfs(graph, nx, ny, [position[0]+i, position[1]+j], n, num) return result def rotate(graph) : n = len(graph) result = [[0]*n for _ in range(n)] for i in range(n): for j in range(n) : result[j][n-1-i] = graph[i][j] return result answer = 0 game_board_copy = copy.deepcopy(game_board) n = len(game_board) blocks = [] for i in range(n) : for j in range(n) : if game_board_copy[i][j] == 0 : game_board_copy[i][j] = 2 blocks.append(dfs(game_board_copy, i, j, [0,0], n, 0)) for _ in range(4) : table = rotate(table) table_rotate_copy = 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 block = dfs(table_rotate_copy, i, j, [0, 0], n, 1) if block in blocks: blocks.pop(blocks.index(block)) answer += len(block) table = copy.deepcopy(table_rotate_copy) else : table_rotate_copy = copy.deepcopy(table) return answer
(참고한 사이트)
https://bladejun.tistory.com/164
프로그래머스 퍼즐 조각 채우기 (python, 파이썬)
문제 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블
bladejun.tistory.com
'알고리즘 > 프로그래머스' 카테고리의 다른 글
프로그래머스 ) 두 큐 합 같게 만들기 (lv.2) (1) 2022.08.30 프로그래머스) 아이템 줍기 (lv.3) (0) 2022.08.21 프로그래머스) 전력망을 둘로 나누기(lv.2) (0) 2022.08.17