[알고리즘/프로그래머스] 퍼즐 조각 채우기

위클리 챌린지 > 퍼즐 조각 채우기

 

코딩테스트 연습 - 퍼즐 조각 채우기

 

나의 풀이

 

- BFS를 사용하여 각 판에 있는 퍼즐 조각 좌표를 찾는다.

같은 퍼즐 조각(또는 빈 자리 조각)끼리 같은 리스트 안에 들어가도록 해줌

그리고 option을 사용하여 game_board는 리스트에서 0을 검사하고 table은 1을 검사한다.

 

- block_rotation 함수는 각 퍼즐 조각 좌표를 시계방향으로 회전시켜주는 역할을 한다.

시계방향으로 좌표 회전 공식 : y ,n-x-1

 

- 비교하려는 퍼즐 조각 좌표들끼리 빼주었을 때 모두 같은 값이 나오면 같은 조각으로 판단

이때 정확히 좌표들을 빼주기 위해서 bfs 함수와 block_rotation 함수에서 좌표를 sort 시켜줌

cnt를 사용하여 개수 카운트

 

- 처음에 같은 퍼즐을 찾으면 바로 remove 시켰는데 그렇게 하면 반복문에서 탐색하지 않는 퍼즐이 생기게 됨

그래서 remove_block에 append 시킨 후 나중에 remove_block 리스트에 없는 퍼즐 조각을 선택하도록 해줌

 

 

처음에는 블럭이 포함되는 직사각형 좌표를 찾으려하다 좌표끼리 차를 계산하여 비교하는 것으로 아이디어를 바꿔서 코드를 작성함