-
1. 풀이
1) 예제 설명
문제 예시에 나온 key 배열과 lock 배열은 다음과 같다.
key 배열
0 0 0
1 0 0
0 1 1
lock 배열
1 1 1
1 1 0
1 0 1
그림으로 나타내면 다음과 같다.
진한 보라색, 노란색 : 돌기
연한 보라색, 노란색 : 홈
=> key의 돌기 부분과 lock의 홈 부분이 만나야 됨
key
lock
즉, 열쇠의 돌기 부분이 자물쇠의 홈 부분에 맞게 채워졌을 때는 아래와 같은 그림이 된다.
진한 선은 lock(자물쇠) 부분에 key(열쇠)가 잘 맞게 채워진 상태를 표현했다.
2) 확장된 lock 배열
이러한 상태를 나타내기 위해서는 확장된 lock 배열을 사용해야 한다.
즉 다음과 같이 표현할 수 있다.
자물쇠는 제 자리에 있고, 열쇠가 이동하면서 자물쇠가 맞게 채워지는지 확인한다.
아래 그림은 열쇠가 자물쇠와 처음 맞게 채워진 경우와,
마지막으로 열쇠와 자물쇠가 맞게 채워지는 경우를 표현한 것이다.
열쇠의 일부가 자물쇠 영역을 벗어나도 된다고 했기 때문에 위와 같이 표현한다.
즉 열쇠와 자물쇠가 겹치는 경우를 표현한다.
위의 그림은
예제의 key, lock 배열이 크기가 3일 때를 표현한 것이다.
그러면 자세히 알아보자.
1. 열쇠의 이동 거리
가로 방향 0 ~ 4, 세로 방향 : 0 ~ 4
이동 거리 구하는 방법
=> 열쇠와 자물쇠가 처음 겹치는 부분 + 자물쇠의 크기
즉, 열쇠가 가로 방향으로 이동할 때
아래 그림에서 시작해서
아래 그림까지 열쇠가 오른쪽으로 4번 이동함을 알 수 있다.
그리고 그 위치는
0열에서 시작해서, 4열까지 이동했다.
세로 방향, 즉 행방향도 마찬가지이다.
위에서
이동 거리 구하는 방법은
열쇠와 자물쇠가 처음 겹치는 부분 + 자물쇠의 크기
라고 했다.
즉, 열쇠와 자물쇠가 처음 겹치는 부분은
아래의 그림에서 분홍색 동그라미 부분을 의미한다.
즉, 2를 의미한다.
그리고 자물쇠의 크기는 3이므로
2+3 = 5 가 된다.
따라서 5미만으로 이동하면
0 ~ 4 가 표현된다.
2. 확장된 lock 배열의 크기
확장된 lock 배열 크기는
자물쇠의 크기 + (열쇠 크기 - 1) * 2 = 7 이다.
=> 3 + (3-1) * 2 = 7
3. 확장된 lock 배열에 입력할 값
확장된 lock 배열에서
열쇠는 이동하고, 자물쇠는 가운데에 위치한다고 했다.
그렇기 때문에 확장된 lock 배열에 자물쇠 배열 값을 똑같이 입력해야 한다.
그 위치는
위쪽 분홍색 동그라미가 위치한 곳에서부터 그대로 입력한다.
4. 자물쇠와 열쇠 크기가 다를 때
key(열쇠) 크기가 2, lock(자물쇠) 크기가 4 일 때
1) 열쇠의 이동 거리
가로 방향 0 ~ 4, 세로 방향 : 0 ~ 4
이동 거리 구하는 방법
=> 열쇠와 자물쇠가 처음 겹치는 부분 + 자물쇠의 크기 = 1 + 4 = 5
2) 확장된 lock 배열 크기
자물쇠의 크기 + (열쇠 크기 - 1) * 2 = 6 이다.
3) 열쇠 회전
열쇠는 회전이 가능하다고 했다.
다음과 같이 배열이 있다고 하자.
<그림 1>
시계 방향으로 90도 회전시키면 다음과 같다.
<그림 2>
원래 배열 인덱스는 아래와 같으므로 인덱스가 어떻게 이동했는지 비교해보자.
즉 <그림 1> 의 노란색 부분 인덱스가 어떻게 변했는지 보면
0,0 => 0,2
1,0 => 0,1
2,0 => 0,0
여기서 규칙을 찾으면
90 도 회전 후 key [ x ][ y ] = 기존 key [ y ][ key 길이 - x - 1 ]
이다.
0,0 => 0,2 부분을 보면
기존 : 0,0
90 도 회전 후 : 0,2
이다.
즉
기존 (x, y) = (0,0)
key 길이 = 3
이므로
회전 후에는
x 값 => 0
y 값 => key 길이 - x - 1 = 3 - 0 - 1 = 2
따라서
(0,2) 가 된다.
4) 자물쇠와 열쇠가 맞게 채워졌는지 확인
돌기는 1로 표시되고, 홈은 0으로 표시된다.
그리고 우리는
key의 돌기 부분과 lock의 홈 부분이 맞게 채워지는지 확인해야 한다.
이때 우리는 key 배열을 이동 시키면서
확장된 lock 배열에
key 배열 값을 더해주면 된다
그 후 확장된 lock 배열 중 자물쇠가 있는 부분이 모두 합이 1이라면 자물쇠와 열쇠가 잘 맞게 채워진 경우이다.
즉 아래의 그림인데,
진한 검은 부분이 확장된 lock 배열 중 자물쇠가 있는 부분이다.
자물쇠는 원래 아래와 같은 상황인데, 진한 보라색은 돌기부분이므로 배열값이 1이고,
연한 보라색은 홈 부분이므로 배열값이 0 이다.
그런데 열쇠를 회전, 이동시키면서
확장된 lock 배열에 key 배열값을 더해준다면,
연한 보라색 부분은 원래 값이 0이었지만 key 배열의 돌기부분, 즉 1을 더해주게 되면서
역시 값이 1이 된다.
그래서 확장된 lock 배열에서 자물쇠가 있는 부분의 모든 값들이 1이 되었다면
열쇠와 자물쇠가 잘 맞게 채워진 경우이다.