프로그래머스. 퍼즐 조각 채우기

tose33 2022. 2. 5. 22:36

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

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

[[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

programmers.co.kr

순수 구현 문제로 코드가 엄청 길어졌다.

일단 내가 문제를 푼 방법은

1. bfs 알고리즘을 이용해 테이블에서 퍼즐 조각들의 좌표를 각각 찾아서 저장한다.

테이블의 좌측상단에서 부터 맞춰볼것이기 때문에 각 퍼즐조각들의 좌표를 좌측상단으로 밀어넣는다.

2. 해당 조각들을 테이블의 좌측상단에서 부터 한칸씩 이동하며 조건에 맞게 테이블에 놓을수 있는지 확인한다.

조건에 맞게 놓을수 있다면 해당 테이블 빈칸을 막아버리고, 해당 퍼즐은 사용처리한다.

3. 테이블을 90도 돌려서 2번을 다시 수행한다.

테이블이 원래 각도가 될때까지 반복한다.

코드가 상당히 길어졌는데 다른 분들은 어떤 방식으로 간결히 풀었는지 찾아봐야겠다.