백준 #15683 - [G4] 감시 : 시뮬레이션, back tracking

(python)

백트래킹 디테일

구현 모듈을 잘 쪼개고, 백트래킹 함수를 잘 작성해주면 되는 문제였습니다. 이전에 작성한 청소년 상어와 결이 비슷합니다. 백트래킹 관련된 부분은 이 글로 대신합니다.

https://jamong-5.tistory.com/53

백준 #19236 - [G2] 청소년 상어 : 구현, back tracking

 

모듈화 아이디어

이 문제의 모듈화 같은 경우, "상하좌우 각 방향의 전체 칸을 모두 탐색한다" 라는 수행이 가장 기본이 되고, 이걸 방향마다 조합하면 한 cctv 의 수행이 됩니다. 고로 각 방향별로 기능을 구현하고 cctv 번호별로 이를 조합한 두겹짜리 이터레이터 (튜플) 를 만들어서 cctv 기능과 회전별 기능을 처리했습니다.

 

+ 저는 안의 내용을 직접 수정하지 않는 경우들을 튜플로 작성하는데, 튜플의 경우 (1) 이렇게 원소 하나만 들어가면 이터레이터가 아닌 단일 원소로 취급하기 때문에 필요한 경우 (1,) 이렇게 컴마로 튜플 형태를 유지해주어야 합니다. 헷갈릴 수 있으니 이런 경우는 list 로 묶는게 나을 수 있겠습니다.

 

코드 구현

import copy
def solution(input) : 
	# 입력 받기
    R,C = list(map(int, input().split()))
    MAP = []
    for _ in range(R) :
        t = list(map(int, input().split()))
        MAP.append(t)
	
    # 맵이 주어졌을 때 사각지대 칸수 세기
    def count_blind_spot(maps) :
        cnt = 0
        for row in maps :
            for i in row :
                if i == 0 :
                    cnt+=1
        return cnt
        
    # 상하좌우 해당 방향 전체 칸 (벽 만나기 전까지) 확인하는 함수들
    def check_right(r,c,maps) :
        for nc in range(c+1,C) :
            if maps[r][nc] == 6 : return
            if maps[r][nc] == 0 : maps[r][nc] = 9
    def check_left(r,c,maps) :
        for nc in range(c-1,-1,-1) :
            if maps[r][nc] == 6 : return
            if maps[r][nc] == 0 : maps[r][nc] = 9
    def check_up(r,c,maps) :
        for nr in range(r-1,-1,-1) :
            if maps[nr][c] == 6 : return
            if maps[nr][c] == 0 : maps[nr][c] = 9
    def check_down(r,c,maps) :
        for nr in range(r+1,R) :
            if maps[nr][c] == 6 : return
            if maps[nr][c] == 0 : maps[nr][c] = 9
            
    # 다음 cctv 찾기
    def next_cctv(r,c,maps) :
        for nr in range(r,R) :
            if nr == r : sc = c+1
            else : sc = 0
            for nc in range(sc,C) :
                if maps[nr][nc] in range(1,6) :
                    return (nr,nc)
        return -1
    
    # 백트래킹 구현
    def back_track(cctv,maps) :
        """ 수도코드
        if 마지막 cctv 까지 다 봤으면 사각지대 갯수 세서 리턴
        for 이 cctv의 모든 배치 각도에 대해서
        	맵 그리기
            다음 씨씨티비 백트래킹
        백트래킹 결과들에 대해 min 리턴
        """
        
        if cctv == -1 :
            return count_blind_spot(maps)
        
        r,c = cctv
        n = maps[r][c]
        
        # cctv 번호별 모든 각도 표현 (안쪽 차원(가장 안쪽 괄호)은 해당 번호 cctv가 한번에 쳐다보는 방향들, 바깥쪽 차원은 회전 경우의 수)
        if n == 1 : check = ((check_right,), (check_up,), (check_left,), (check_down,))
        elif n == 2 : check = ((check_right,check_left,), (check_up,check_down),)
        elif n == 3 : check = ((check_right,check_up), (check_up, check_left,), (check_left,check_down,), (check_down,check_right,))
        elif n == 4 : check = ((check_right, check_up, check_left,), (check_up,check_left,check_down,),(check_left,check_down,check_right,),(check_down,check_right,check_up,))
        elif n == 5 : check = ((check_right,check_up,check_left,check_down,),)

        ncctv = next_cctv(r,c,maps)

        back_track_results = []
        for runs in check :
            nmap = copy.deepcopy(maps)
            for run in runs :
                run(r,c,nmap)
            result = back_track(ncctv, nmap)
            back_track_results.append(result)

        return min(back_track_results)


    cctv = next_cctv(0,-1,MAP)
    print(back_track(cctv, MAP))
    
solution(input)