거의 다... 교재 코드를 참고했습니다 ㅜ.ㅜ

60059 자물쇠와 열쇠

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

생각

이동할 수 있는 최대 횟수 18x18
회전 4
총 계산 횟수 4x18x18
완전 탐색으로 진행해도 될 것 같다!

처음 한 생각

회전 -> 이동 -> 검사

회전과 이동을 통해 new_key를 만든다, 그리고 해당 키가 lock과 맞는지 검사한다.
-> 회전이 너무 어려워서 교재를 참고해야겠다 생각.

교재의 구현 방법

• 이동
  매 이동과 회전마다 새로운 키를 만드는게 아니라, 새로운 자물쇠를 만들어 거기에 키를 검사해준다.
  
  lock보다 세배 큰 new_lock를 만들어 중간에만 기존의 lock 값을 넣어준다.
  그리고 key를 new_lock의 1~n*3-1 범위까지 한번씩 넣어본다.

• 회전

def rotate(k):
    n=len(k)
    result=[[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            result[j][n-i-1]=k[i][j]
    return result

회전이 코드로만 보면 잘 이해가 안가서...ㄱ- 직접 그렸다.
확실히 무식하게 그려보는게 이해가 가긴 하는듯

• 확인
  넣어보는 행위는 new_lock의 값에 key를 더해주는 거로 하기 때문에,
  열쇠와 자물쇠가 같다면 new_lock의 중간 부분이 모두 1이 되어야 한다.
  그러므로 new_lock의 중간 부분 n~n*2이 모두 1인지 확인한다.

코드

#회전
def rotate(k):
    n=len(k)
    result=[[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            result[j][n-i-1]=k[i][j]
    return result
    
#확인
def check(l):
    n=len(l)//3
    #new_lock의 중간 부분이 모두 1인지 확인
    for i in range(n,n*2):
        for j in range(n,n*2):
            if l[i][j]!=1:
                return False
    return True
                

def solution(key, lock):
    answer = False
    n=len(lock)
    m=len(key)
    
    new_lock = [[0]*(n*3) for _ in range(n*3)]
    #세배 확장된 lock을 만든다.
    for i in range(n):
        for j in range(n):
            new_lock[i+n][j+n]=lock[i][j]
            
    #매 회전
    for r in range(4):
        key=rotate(key)
        #매 이동
        for x in range(1,n*2):
            for y in range(1,n*2):
            
            	#열쇠를 넣어준다.
                for i in range(m):
                    for j in range(m):
                    	#lock에 key를 더해줌
                        new_lock[x+i][y+j]+=key[i][j]
                
                #해당 열쇠가 맞는지 검사
                if check(new_lock)==True:
                    return True
                    
                #맞지 않는다면 되돌린다(열쇠를 뺀다)
                for i in range(m):
                    for j in range(m):
                        new_lock[x+i][y+j]-=key[i][j]
    
    return False

60061 기둥과 보 설치

https://programmers.co.kr/learn/courses/30/lessons/60061

생각

처음 한 생각

wall 이라는 2차원 리스트를 만든다. -> build_frame 에서 작업 하나씩 읽어온다. -> 해당 좌표 주변의 wall을 보며 조건에 맞는지 확인한다. -> 조건에 부합하면 wall에 넣어준다. -> build_frame을 모두 읽었으면, wall을 확인해서 기둥과 보의 좌표를 answer에 넣어준다.

wall은 해당 사진처럼 구현하려고 했는데유, 생각해보니 기둥과 보를 저장을 하려면 '칸'이 아니라 '변'에 저장을 해야하는데, 보가 존재할 수 있는 변의 행은 홀수행, 열은 n개, 기둥이 존재할 수 있는 변의 행은 짝수행, 열은 n+1개...? 막 이런식으로 너무 세세해져서 나약하지만 포기하고 교재를 참고했습니다.

교재의 구현 방법

완전 탐색!!

build_frame 확인 -> 일단 answer에 반영한다. -> 조건에 맞는지 확인한다 (answer을 모두 탐색해가며) -> 맞으면 그대로 두고 틀리면 되돌린다.

코드

#기둥 -> 바닥 위, 보의 한쪽 끝부분 위, 다른 기둥 위
#보 -> 한쪽 끝부분이 기둥 위, 양쪽 끝부분이 보와 동시에 연결
#[가로 좌표,세로 좌표,기둥과 보,삭제와 설치]
#[가로 좌표, 세로 좌표, 기둥과 보] -> x좌표 기준으로 오름차순 , y 좌표 기준, 기둥
#입력을 읽어와 -> 일단 넣어-> 조건에 맞는지 확인 -> 안맞으면 되돌려

#조건에 맞는지 확인
def check(answer):
    for x,y,a in answer:
        #x좌표 y좌표 a 기둥과보
        if a==0: #기둥
            if y!=0 and [x,y-1,0] not in answer and [x-1,y,1] not in answer and [x,y,1] not in answer:
                return False
        else: #보
            if [x,y-1,0] not in answer and [x+1,y-1,0] not in answer and not ([x-1,y,1] in answer and [x+1,y,1] in answer):
                return False
    return True

def solution(n, build_frame):
    answer = []
    while(build_frame):
        x,y,a,b=build_frame.pop(0)
        #삭제일경우
        if b==0:
        	#일단 삭제
            answer.remove([x,y,a])
            if not check(answer): #조건에 부합한지 확인
                answer.append([x,y,a])
        #설치일 경우
        else:
        	#일단 설치
            answer.append([x,y,a])
            if not check(answer): #조건에 부합한지 확인
                answer.remove([x,y,a])
    answer.sort()
    return answer

60062 외벽 점검

https://programmers.co.kr/learn/courses/30/lessons/60062

생각

처음 한 생각

수학적으로 풀 수 있지 않을까?
입력받은 weak의 최단 거리를 구하고, 해당 최단거리가 dist보다 작은지 확인 되지 않을까?!

인원이 한명이라고 가정하고 weak를 모두 지날 수 있는 최단거리 구하기 -> 그게 dist중 하나보다 작은지 확인 -> 크다면 인원수를 하나씩 늘림...

을 반복하면 되지 않을까?!
했는데
두명 이상이 됐을때부터 너무너무너무 복잡해짐... (weak를 n가지 범위로 나누는 경우의 수, dist를 n개 고르는 경우의 수...)
그래서 교재를 참고하였습니다 나약해서 죄송합니다......

교재의 구현 방법

이역시 완전 탐색!!

• 원형
  dist를 두번 반복해 나열해 원형을 일자 형태로 만든다.
• 구현
  모든 시작점 에서의
  (모든 시작점은 dist를 구성하는 모든 취약점을 말한다.)
  친구를 나열하는 모든 경우의 수 를 나열한 후 완전탐색한다

코드

from itertools import permutations

def solution(n, weak, dist):
    
    #원형을 일자 형태로 변형하기
    length=len(weak)
    for i in range(length):
        weak.append(weak[i]+n)
    
    answer=len(dist)+1
    
    #모든 시작점을 탐색한다.
    for start in range(length):
        
        #친구를 나열하는 모든 경우를 탐색한다.
        for friends in list(permutations(dist,len(dist))):
            
            count=1#친구의 수
            
            #해당 친구가 점검할 수 있는 마지막 위치
            position=weak[start]+friends[count-1]
            
            #시작점부터 취약한 지점 확인
            for index in range(start,start+length):
                #해당 취약한 지점이 현재 친구로 점검할 수 있는 최대의 위치를 벗어날 경우
                if position<weak[index]:
                    #새로운 친구 투입한다.
                    count+=1
                    #친구수가 부족하다면 종료한다.
                    if count>len(dist):
                        break
                    #position 업데이트 (새로운 친구 투입됐으니)
                    position = weak[index]+friends[count-1]
                    
            answer=min(answer,count) #최소값 계산
            
    if answer>len(dist):
        return -1
    return answer