[삼성SW역량][Python/BOJ] 백준 15683 감시_(DFS+구현)

🐾 20220917

 

 

 

행복하고 재밌는 DFS 문제다. ^^ 

 

 

 

 

1,2,3,4 CCTV 마다 볼수있는 방향이 다르다.

이를 미리 cctv_dir으로 설정해 놓는다. 

 

 

 

 

1. 주어진 그래프를 돌면서 cctv가 있는 곳의 위치와 번호를 저장한다. 

2. DFS에 그래프와 횟수를 인수로 넘긴다.

2-1.  종료 조건은 모든 cctv를 탐색한 경우이다. 

2-2. 현재의 그래프와 동일하지만 객체는 다른 지도를 만든다.  (원본 배열의 보존을 위해) [copy.deepcopy이용]

2-3. cctv의 타입에 따라 갈 수 있는 방향을 돌면서  감시가능 영역을 설정한다. 

2-4. DFS를 이용해 재귀적으로 탐색할 수 있도록 만든다. 

2-5. 원본 배열에서 deepcopy를 통해 감시 전으로 돌아갈 수 있도록 만든다. 

 

 

 

CCTV를 발견할 때마다 dfs를 돌리는 것이 아니라 다 모은 후에 DFS를 돌린다. 

 

 

 

 

코드 : 

import copy
        
# 상 하 좌 우     
dx = [-1,1,0,0]
dy = [0,0,-1,1]

cctv_dir = [
    [],
    [[0],[1],[2],[3]], # 1번 cctv 
    [[0,1], [2,3]], # 2번 cctv 
    [[0,2],[2,1],[1,3],[3,0]], # 3번 cctv 
    [[0,3,1], [3,1,2],[1,2,0],[2,0,3]], # 4번 cctv 
    [[0,1,2,3]] # 4번 cctv 
]    

# depth번째 cctv가 볼 수 있는곳 표시 
def dfs(mp, depth) :
    global ans 
    
    if depth == len(cctv) : 
        ans = min (ans, count_zero(mp))
        return 
    else : 
        mp_copy = copy.deepcopy(mp)
        
        # depth번째 cctv 정보 얻기 
        x,y,cctv_type = cctv[depth]

        for dir in cctv_dir[cctv_type] :
            # [볼 수 있는 곳을 '#'로 변경시키고]
            watch(x,y,dir,mp)
            
			# 다음 cctv를 처리하러 갑니다. 
            dfs(mp, depth+1)
            
            # 여기에 왔으면 depth == len(cctv)를 지났음 
            # stack 구조상 가장 위에 함수가 pop된 상태 
            # 기존의 mp 상태를 보존중이던 mp_copy를 다시 mp에 복사 
            mp = copy.deepcopy(mp_copy)
        
def watch(x,y,dir,mp) :
    # 바라볼 방향들을 돌면서 
    for d in dir :
    	# 원래 위치에서
        nx,ny = x,y 
        while True :
            nx ,ny = nx+ dx[d], ny+dy[d]
            if 0<=nx<n and 0<=ny<m :
                if mp[nx][ny] == 6 : break
                elif mp[nx][ny] == 0 :
                    mp[nx][ny] = '#'
            else : break
# 사각지대의 개수 세기 
def count_zero(mp) :
    cnt = 0
    for i in mp :
        cnt += i.count(0)
    return cnt                   
    
if __name__=="__main__" :
    n,m = map(int,input().split())
    mp = [list(map(int,input().split())) for _ in range(n)]

    ans = int(1e9)
    cctv = []
    for i in range(n) :
        for j in range(m) :
       		 # cctv를 발견하면 
            if 1<=mp[i][j]<=5 :
                cctv.append([i,j,mp[i][j]])
    # 0번째 cctv가 볼수있는 곳 탐색 & 표시 
    dfs(mp,0)
    print(ans)

 

 

 

 

 

 

 

참고 블로그 :

https://heytech.tistory.com/373

[DFS] 백준#15683: 감시/Python