링크

퍼즐조각 채우기

난이도

  • 프로그래머스 난이도 3
    • 문제가 내준것은 쉬워보이지만 실제 구현할게 엄청 많음
    • 위클리 문제로 대충 3에서 4사이로 생각

문제요약

  • 빈칸에 주어진 도형을 최대로 채우는 빈칸의 수를 구하기
    • 빈칸과 같은 모양의 도형을 넣어야한다.
    • 도형은 회전은 되지만 뒤짚는것은 안된다.

접근

  • 주어진 조건에 맞게 구현하기
  • 빈칸과 도형은 bfs를 이용해서 도형을 찾는다.
  • 빈칸과 주어진 모든 도형을 비교, 회전하여 맞는 도형을 찾는다.
  • 맞춰진 도형이 채운 빈칸을 센다.

간단 알고리즘

  • 여러개의 모듈이 존재
  • ratate90,180
    • 행렬을 90도 180도 회전해준다.
  • bfs
    • 행렬을 돌면서 bfs로 도형 / 빈칸을 추출한다.
    • 추출한 도형은 그 도형에 맞는 직사각형 행렬에 넣어준다.
      • [0,0],[1,1],[0,1]도형의 좌표가 이럴때 [[1,1],[0,1]]이런식으로 도형의 모양을 나타내는 직사각형 행렬로 만든다.
    • 각 도형마다 그 도형의 블럭 갯수도 나중을 위해 저장해준다
  • tablecheck
    • 테이블의 도형이 사용되었는지 확인하는 배열
    • 미사용시0, 사용시1로 한다.
  • game_board(빈칸인0을 도형으로 생각해서 추출), table(1을 기준으로 도형 추철)에 각 bfs를 적용하여 도형 추출
  • game_board의 도형을 기준으로 모든 table도형과 비교
    • table도형이 사용안되었을때를 전재로 시작
    • 가로와 세로가 각각 같을때
      • 원본상태 비교
      • 180도 회전후 비교
    • 가로 세로가 각각 세로 가로와 같을때
      • 90도 회전후 비교
      • 90도 회전한것에 다시 180회전후 비교
    • 맞으면 tablecheck에 1로 표시

후기

  • 너무 오래걸리는 문제.
  • 구현하는 알고리즘을 생각하는것은 크게 어렵지 않았다.
  • 큰 기교를 원하는것도 없고 특별한 자료구조를 생각하지 않아도 충분히 풀리는 문제 그래서 난이도 3정도
  • 하지만 만약 코딩테스트에서 이런 문제가 나오면 빠르게 구현하는 연습을 해야하지만, 손과 머리가 약간 느린 나로서는 너무 어려운 문제였다.
  • 좀더 빠르게 코딩하고 디버깅을 해야하는 훈련이 필요한 문제였다.