백준_15683_감시 (python)

※ 접근법

 N,M의 크기가 크지 않아 완전 탐색을 해야겠다고 생각했고 CCTV 감시 방향이 4방향인 것을 보고 재귀를 이용해 백트래킹 해야겠다고 생각했다. 

 

※ 풀이

1. 좌표 0,0부터 차례차례 하나씩 탐색을 해나간다. 

2. 현재 탐색중인 좌표에 CCTV가 있다면 감시를 하고 감시한곳은 1을 빼준다.

3. 1번과 2번을 반복하다가 r의 크기가 N과 같아졌다면 사각지대의 개수를 구해주고 백트래킹을 한다.

4. 다음 감시 방향으로 넘어가기 전에 감시했던 방향을 +1을 해줘 감시를 풀어준다.

N,M = map(int,input().split())
data = [list(map(int,input().split())) for _ in range(N)]
min_num = float("inf")

def one_cctv(r,c,visited,flag):
    dx = [0,-1,0,1]
    dy = [1,0,-1,0]
    while True:
        nx = r + dx[flag]
        ny = c + dy[flag]
        if 0 <= nx < N and 0 <= ny < M:
            if visited[nx][ny] == 6: # 벽이라면 바로 탈출
                break
            if visited[nx][ny] <= 0:
                visited[nx][ny] -= 1
            r,c = nx,ny
        else:
            break

def one_cctv_clear(r,c,visited,flag):
    dx = [0,-1,0,1]
    dy = [1,0,-1,0]
    while True:
        nx = r + dx[flag]
        ny = c + dy[flag]
        if 0 <= nx < N and 0 <= ny < M:
            if visited[nx][ny] == 6: # 벽이라면 바로 탈출
                break
            if visited[nx][ny] < 0:
                visited[nx][ny] += 1
            r,c = nx,ny
        else:
            break

def two_cctv(r,c,visited,flag):
    dx = [(0,0), (-1,1)]
    dy = [(-1,1), (0,0)]
    tr,tc = r,c
    for i in range(2):
        r,c = tr,tc
        while True:
            nx = r + dx[flag][i]
            ny = c + dy[flag][i]
            if 0 <= nx < N and 0 <= ny < M: # 계쏙 범위 안에 있나
                if visited[nx][ny] == 6: # 벽이라면 바로 탈출
                    break
                if visited[nx][ny] <= 0:
                    visited[nx][ny] -= 1
                r,c = nx,ny
            else:
                break # 계속 더하기 때문에 범위 안에 계속 있을 수가 없어 

def two_cctv_clear(r,c,visited,flag):
    dx = [(0,0), (-1,1)]
    dy = [(-1,1), (0,0)]
    tr,tc = r,c
    for i in range(2):
        r,c = tr,tc
        while True:
            nx = r + dx[flag][i]
            ny = c + dy[flag][i]
            if 0 <= nx < N and 0 <= ny < M:
                if visited[nx][ny] == 6: # 벽이라면 바로 탈출
                    break
                if visited[nx][ny] < 0:
                    visited[nx][ny] += 1
                r,c = nx,ny
            else:
                break

def three_cctv(r,c,visited,flag):
    dx = [(-1,0), (0,1), (1,0), (0,-1)]
    dy = [(0,1), (1,0), (0,-1), (-1,0)]
    tr,tc = r,c
    for i in range(2):
        r,c = tr, tc
        while True:
            nx = r + dx[flag][i]
            ny = c + dy[flag][i]
            if 0 <= nx < N and 0 <= ny < M:
                if visited[nx][ny] == 6: # 벽이라면 바로 탈출
                    break
                if visited[nx][ny] <= 0:
                    visited[nx][ny] -= 1
                r,c = nx,ny
            else:
                break

def three_cctv_clear(r,c,visited,flag):
    dx = [(-1,0), (0,1), (1,0), (0,-1)]
    dy = [(0,1), (1,0), (0,-1), (-1,0)]
    tr,tc = r, c
    for i in range(2):
        r, c = tr, tc
        while True:
            nx = r + dx[flag][i]
            ny = c + dy[flag][i]
            if 0 <= nx < N and 0 <= ny < M:
                if visited[nx][ny] == 6: # 벽이라면 바로 탈출
                    break
                if visited[nx][ny] < 0:
                    visited[nx][ny] += 1
                r,c = nx,ny
            else:
                break

def four_cctv(r,c,visited,flag):
    dx = [(0,-1,0), (-1,0,1), (0,1,0), (1,0,-1)]
    dy = [(-1,0,1), (0,1,0), (1,0,-1), (0,-1,0)]
    tr, tc = r, c
    for i in range(3):
        r, c = tr, tc
        while True:
            nx = r + dx[flag][i]
            ny = c + dy[flag][i]
            if 0 <= nx < N and 0 <= ny < M:
                if visited[nx][ny] == 6: # 벽이라면 바로 탈출
                    break
                if visited[nx][ny] <= 0:
                    visited[nx][ny] -= 1
                r,c = nx,ny
            else:
                break

def four_cctv_clear(r,c,visited,flag):
    dx = [(0,-1,0), (-1,0,1), (0,1,0), (1,0,-1)]
    dy = [(-1,0,1), (0,1,0), (1,0,-1), (0,-1,0)]
    tr, tc = r ,c
    for i in range(3):
        r,c = tr, tc
        while True:
            nx = r + dx[flag][i]
            ny = c + dy[flag][i]
            if 0 <= nx < N and 0 <= ny < M:
                if visited[nx][ny] == 6: # 벽이라면 바로 탈출
                    break
                if visited[nx][ny] < 0:
                    visited[nx][ny] += 1
                r,c = nx,ny
            else:
                break

def five_cctv(r,c,visited,flag):
    dx = [(0,-1,0,1)]
    dy = [(-1,0,1,0)]
    tr, tc = r, c
    for i in range(4):
        r,c = tr, tc
        while True:
            nx = r + dx[flag][i]
            ny = c + dy[flag][i]
            if 0 <= nx < N and 0 <= ny < M:
                if visited[nx][ny] == 6: # 벽이라면 바로 탈출
                    break
                if visited[nx][ny] <= 0:
                    visited[nx][ny] -= 1
                r,c = nx,ny
            else:
                break

def five_cctv_clear(r,c,visited,flag):
    dx = [(0,-1,0,1)]
    dy = [(-1,0,1,0)]
    tr,tc = r, c
    for i in range(4):
        r,c = tr, tc
        while True:
            nx = r + dx[flag][i]
            ny = c + dy[flag][i]
            if 0 <= nx < N and 0 <= ny < M:
                if visited[nx][ny] == 6: # 벽이라면 바로 탈출
                    break
                if visited[nx][ny] < 0:
                    visited[nx][ny] += 1
                r,c = nx,ny
            else:
                break

def solve(r,c,data):
    global min_num
    if c == M:
        c = 0
        r += 1
    if r == N:
        count = 0
        for i in range(N):
            for j in range(M):
                if data[i][j] == 0:
                    count += 1
        min_num = min(min_num,count)
        return
    if 1 <= data[r][c] <= 5:       
        if data[r][c] == 1:
            one_cctv(r,c,data,0)
            solve(r,c+1,data)
            one_cctv_clear(r,c,data,0)
            one_cctv(r,c,data,1)
            solve(r,c+1,data)
            one_cctv_clear(r,c,data,1)
            one_cctv(r,c,data,2)
            solve(r,c+1,data)
            one_cctv_clear(r,c,data,2)
            one_cctv(r,c,data,3)
            solve(r,c+1,data)
            one_cctv_clear(r,c,data,3)
        if data[r][c] == 2:
            two_cctv(r,c,data,0)
            solve(r,c+1,data)
            two_cctv_clear(r,c,data,0)
            two_cctv(r,c,data,1)
            solve(r,c+1,data)
            two_cctv_clear(r,c,data,1)
        if data[r][c] == 3:
            three_cctv(r,c,data,0)
            solve(r,c+1,data)
            three_cctv_clear(r,c,data,0)
            three_cctv(r,c,data,1)
            solve(r,c+1,data)
            three_cctv_clear(r,c,data,1)
            three_cctv(r,c,data,2)
            solve(r,c+1,data)
            three_cctv_clear(r,c,data,2)
            three_cctv(r,c,data,3)
            solve(r,c+1,data)
            three_cctv_clear(r,c,data,3)
        if data[r][c] == 4:
            four_cctv(r,c,data,0)
            solve(r,c+1,data)
            four_cctv_clear(r,c,data,0)
            four_cctv(r,c,data,1)
            solve(r,c+1,data)
            four_cctv_clear(r,c,data,1)
            four_cctv(r,c,data,2)
            solve(r,c+1,data)
            four_cctv_clear(r,c,data,2)
            four_cctv(r,c,data,3)
            solve(r,c+1,data)
            four_cctv_clear(r,c,data,3)
        if data[r][c] == 5:
            five_cctv(r,c,data,0)
            solve(r,c+1,data)
            five_cctv_clear(r,c,data,0)
    else:
        solve(r,c+1,data)
    
solve(0,0,data)
print(min_num)

 

※ 회고

 테케 3,4 번만 통과가 안 됐엇다. 원래는 감시구역을 해제할 때 visited[nx][ny] == -1이라면 visited[nx][ny] = 0이라고 했었다. 하지만 한 구역을 여러 감시 카메라가 감시하고 있었다면 한 구역이 다 같이 해제가 된다.

 3,4번만 통과가 되지 않았을 때 왜 안 되는지 1,2,5,6과 3,4번의 차이가 무엇인지 더 고민해봤어야 했다.