문제:
풀이방법:
생각보다 시간에 대한 조건이 넉넉한 편이기 때문에 모든 경우의 수를 확인하면서 풀어도 된다.
가능한 모든 경우의 수를 구하기 위해서 key와 lock의 크기를 기준으로 a라는 배열을 만든다. key와 lock의 크기가 3x3으로 동일하다고 하면 다음과 같이 a를 만들어야 한다.
위 그림에서 노란색으로 색칠한 부분이 lock에 해당하고, 빨간색 박스가 key에 해당한다. 이제 이 배열에서 빨간색 박스 key로 a를 슬라이딩하면서 lock에 해당하는 부분이 모두 채워지는 경우가 있는지 확인하면 된다.
따라서 a를 (len(key)*2+len(lock)-2)x(len(key)*2+len(lock)-2) 크기인 0인 2차원 배열로 초기화 하고 lock에 해당하는 부분만 채워주도록 한다.
위 그림부터 시작해서 현재 key 모양, 90도 회전한 모양, 180도 회전한 모양, 270도 회전한 모양을 각각 넣어보면서(360도는 현재 key 모양과 같다.) lock의 모든 값이 1로 바뀌었는지 확인한다.
이 확인 과정을 슬라이딩 끝까지 진행하며 중간에 True인 경우가 있다면 바로 true를 반환한다. 만약 끝까지 true인 경우가 없다면 false를 반환한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
import copy
def check(x,y,a,key,x1,y1,lock):
temp=copy.deepcopy(a)
for i in range(len(key)):
for j in range(len(key)):
temp[x+i][y+j]+=key[i][j]
if solve(x1,y1,temp,lock):
return True
else:
return False
def solve(x,y,a,lock):
for i in range(len(lock)):
for j in range(len(lock)):
if a[x+i][y+j]==0 or a[x+i][y+i]==2:
return False
return True
def rotate_90(m):
N = len(m)
ret = [[0] * N for _ in range(N)]
for r in range(N):
for c in range(N):
ret[c][N-1-r] = m[r][c]
return ret
def rotate_180(m):
N = len(m)
ret = [[0] * N for _ in range(N)]
for r in range(N):
for c in range(N):
ret[N-1-r][N-1-c] = m[r][c]
return ret
def rotate_270(m):
N = len(m)
ret = [[0] * N for _ in range(N)]
for r in range(N):
for c in range(N):
ret[N-1-c][r] = m[r][c]
return ret
def solution(key,lock):
a=[[0 for i in range(len(key)*2+len(lock)-2)]for i in range(len(key)*2+len(lock)-2)]
x=len(key)-1
y=len(key)-1
for i in range(len(lock)):
for j in range(len(lock)):
a[x+i][y+j]=lock[i][j]
for i in range(len(a)-len(key)+1):
for j in range(len(a)-len(key)+1):
if check(i,j,a,key,x,y,lock):
return True
key90=rotate_90(key)
if check(i,j,a,key90,x,y,lock):
return True
key180=rotate_180(key)
if check(i,j,a,key180,x,y,lock):
return True
key270=rotate_270(key)
if check(i,j,a,key270,x,y,lock):
return True
return False
|
cs |
문제링크:
https://programmers.co.kr/learn/courses/30/lessons/60059
코딩테스트 연습 - 자물쇠와 열쇠
[[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true
programmers.co.kr
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]14502. 연구소 (0) | 2020.08.18 |
|---|---|
| [BOJ]2961. 도영이가 만든 맛있는 음식 (0) | 2020.08.13 |
| [BOJ]2493. 탑 (0) | 2020.08.06 |
| [BOJ]19532. 수학은 비대면강의입니다. (0) | 2020.08.04 |
| [BOJ]2580. 스도쿠 (0) | 2020.07.30 |