60059: 자물쇠와 열쇠

Link : programmers.co.kr/learn/courses/30/lessons/60059

---

1. 문제

• 고고학자인 튜브는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.

  잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.

  자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.

  열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.

 

---

2. 문제의 조건

• key = M * M (3 <= M <= 20) 2차원 배열
• lock = N * N (3 <= N <= 20) 2차원 배열
• M <= N
• 돌기 부분이 겹치면 안됨

 

---

3. 문제 접근

• 아이디어
  
  해당 문제는 2차원 lock에 대해 key의 각도(0, 90, 180, 270)를 바꾸고 하나하나 끝까지 대입해보면 해결할 수 있다고 생각하였습니다.
  
  우선 대입을 하기 위해서 새로운 map인 board는 Key * 2 + Lock - 2 의 보드판이 필요합니다.
  

  

  
  파란색으로 둘러쌓인 부분만 탐색하면 되기 떄문입니다. 하지만 소스코드상 편의를 위해 Key * 2 + Lock으로 범위를 지정하였습니다.
  맨처음 1,1 부터 Key를 탐색합니다. 첫번째 빨간색은 Key의 범위로 Lock과 부딪혀보면 파란색이 중복되는것을 알 수 있고, 검정색 안의 흰색이 전부 가려지지 않았습니다. 그러므로 1,1(X, Y) 에선 False입니다.
  2, 1)도 마찬가지 ...  (5, 5)까지 탐색하면 마무리가 됩니다. 이 때, Key를 90를 회전합니다.
  그리고 반복합니다. 이렇게 0도 90도 180도 270도를 가지고 비교하시면 됩니다.

 

---

4. 풀이 방법

• Key의 길이과 Lock의 길이를 얻어옵니다.
• board 라는 2차원배열의 길이를 K * 2 + L 로 만들어줍니다.
• 0, 90, 180, 270도 총 4번을 회전해야하니 for문으로 4번을 탐색합니다.
• 그림에서 나오듯 1,1 부터 K + L 의 길이만큼 반복합니다. - 4
  (끝까지 탐색하기 위해서 K + L임)
• 새로운 board를 깊은복사로 하나 만들어줍니다.
• Key만큼을 새로운 t_board[y][x]에 더해줍니다.
• 다 더해지면 해당 키가 겹쳐져있는지 아닌지 판단합니다.
  확인은 for로 Lock의 길이만큼 1이 아닌것이 있으면 False입니다. (겹쳤거나 메꾸지 못했거나)
• 0도의 크기로 모든 y,x 를탐색했는데 True가 반환되지 않았으므로 90도를 회전합니다.
• 4로 돌아가서 시작합니다.

 

---

5. 소스코드

• cjw-git.tistory.com/141

 

---

 

cjw.git@gmail.com