이번 문제는 삼성 기출 문제로 백트레킹과 구현을 통해 해결하였다. 처음에 백트레킹을 생각했지만, 브루트포스로도 해결이 가능할 것이라 생각하였고, 브루트포스로 구현을 하였다. cctv의 위치와 종류를 튜플로 하여 cctvs리스트에 담고, 이를 종류의 내림차순으로 정렬한 후에 cctv가 볼 수 있는 구간의 크기를 모두 구하여 이 중 큰 것을 따라가도록 구현하였다.

n, m=map(int, input().split())
grid=[list(map(int, input().split())) for _ in range(n)]
dy, dx=[0, 1, 0, -1], [1, 0, -1, 0]
cctv=[[0 for _ in range(m)] for _ in range(n)]
cctvs=[]
for i in range(n):
    for j in range(m):
        if 0<grid[i][j]<6:
            cctvs.append((i, j, grid[i][j]))
            cctv[i][j]=-1
cctvs.sort(key=lambda x: x[2], reverse=True)
def monitoring(sy, sx):
    if grid[sy][sx]==1:
        cnt=[0 for _ in range(4)]
        for i in range(4):
            ny, nx=sy+dy[i], sx+dx[i]
            while 0<=ny<n and 0<=nx<m and grid[ny][nx]!=6:
                if cctv[ny][nx]==0:
                    cnt[i]+=1
                ny+=dy[i]
                nx+=dx[i]
        d=cnt.index(max(cnt))
        ny, nx=sy+dy[d], sx+dx[d]
        while 0<=ny<n and 0<=nx<m and grid[ny][nx]!=6:
            cctv[ny][nx]=-1
            ny+=dy[d]
            nx+=dx[d]
    elif grid[sy][sx]==2:
        cnt=[0 for _ in range(2)]
        for i in range(2):
            ny1, nx1=sy+dy[i], sx+dx[i]
            while 0<=ny1<n and 0<=nx1<m and grid[ny1][nx1]!=6:
                if cctv[ny1][nx1]==0:
                    cnt[i]+=1
                ny1+=dy[i]
                nx1+=dx[i]
            ny2, nx2=sy-dy[i], sx-dx[i]
            while 0<=ny2<n and 0<=nx2<m and grid[ny2][nx2]!=6:
                if cctv[ny2][nx2]==0:
                    cnt[i]+=1
                ny2-=dy[i]
                nx2-=dx[i]
        d=cnt.index(max(cnt))
        ny1, nx1=sy+dy[d], sx+dx[d]
        while 0<=ny1<n and 0<=nx1<m and grid[ny1][nx1]!=6:
            cctv[ny1][nx1]=-1
            ny1+=dy[d]
            nx1+=dx[d]
        ny2, nx2=sy-dy[d], sx-dx[d]
        while 0<=ny2<n and 0<=nx2<m and grid[ny2][nx2]!=6:
            cctv[ny2][nx2]=-1
            ny2-=dy[d]
            nx2-=dx[d]
    elif grid[sy][sx]==3:
        cnt=[0 for _ in range(4)]
        for i in range(4):
            ny1, nx1=sy+dy[i], sx+dx[i]
            while 0<=ny1<n and 0<=nx1<m and grid[ny1][nx1]!=6:
                if cctv[ny1][nx1]==0:
                    cnt[i]+=1
                ny1+=dy[i]
                nx1+=dx[i]
            ny2, nx2=sy+dy[(i+1)%4], sx+dx[(i+1)%4]
            while 0<=ny2<n and 0<=nx2<m and grid[ny2][nx2]!=6:
                if cctv[ny2][nx2]==0:
                    cnt[i]+=1
                ny2+=dy[(i+1)%4]
                nx2+=dx[(i+1)%4]
        d=cnt.index(max(cnt))
        ny1, nx1=sy+dy[d], sx+dx[d]
        while 0<=ny1<n and 0<=nx1<m and grid[ny1][nx1]!=6:
            cctv[ny1][nx1]=-1
            ny1+=dy[d]
            nx1+=dx[d]
        ny2, nx2=sy+dy[(d+1)%4], sx+dx[(d+1)%4]
        while 0<=ny2<n and 0<=nx2<m and grid[ny2][nx2]!=6:
            cctv[ny2][nx2]=-1
            ny2+=dy[(d+1)%4]
            nx2+=dx[(d+1)%4]
    elif grid[sy][sx]==4:
        cnt=[0 for _ in range(4)]
        for i in range(4):
            for j in range(4):
                if i==j:
                    continue
                ny, nx=sy+dy[j], sx+dx[j]
                while 0<=ny<n and 0<=nx<m and grid[ny][nx]!=6:
                    if cctv[ny][nx]==0:
                        cnt[i]+=1
                    ny+=dy[j]
                    nx+=dx[j]
        d=cnt.index(max(cnt))
        for i in range(4):
            if i==d:
                continue
            ny, nx=sy+dy[i], sx+dx[i]
            while 0<=ny<n and 0<=nx<m and grid[ny][nx]!=6:
                cctv[ny][nx]=-1
                ny+=dy[i]
                nx+=dx[i]
    elif grid[sy][sx]==5:
        for i in range(4):
            ny, nx=sy+dy[i], sx+dx[i]
            while 0<=ny<n and 0<=nx<m and grid[ny][nx]!=6:
                cctv[ny][nx]=-1
                ny+=dy[i]
                nx+=dx[i]
for y, x, _ in cctvs:
    monitoring(y, x)
answer=0
for i in range(n):
    for j in range(m):
        if grid[i][j]==0 and cctv[i][j]==0:
            answer+=1
print(answer)

그러나 17%에서 오답처리 되었다. 찾지 못한 반례가 존재하였고, 이를 해결하기 위해 노력하였지만 해결하지 못하였다. 그래서 모든 방법을 확실하게 확인하는 백트레킹으로 구현해보기로 하였다. cctv를 1부터 5까지 함수로 구현하였다. cctv가용범위는 위에서 작성한 코드를 그대로 사용하였다.

• cctv1의 경우 4가지 케이스로 구동할 수 있다.
• cctv2의 경우 2가지 케이스로 구동할 수 있다.
• cctv3의 경우 4가지 케이스로 구동할 수 있다.
• cctv4의 경우 4가지 케이스로 구동할 수 있다.
• cctv5의 경우 1가지 케이스로 구동할 수 있다.

모든 케이스들을 setting함수에서 백트레킹으로 구현하였다. 그리고 idx가 cctvs의 길이와 같을 경우에 counting함수를 통해 grid와 cctv를 순회하며 둘 다 0일 경우에만 카운팅 변수를 증가시켜 반환시키고, 이 반환값과 기존의 값 중 최솟값을 취하도록 하였다.

이 특징들을 이용하여 백트레킹 코드를 구현하였고, 반례에서 벗어날 수 있었다.

Code

import sys
from copy import deepcopy
n, m=map(int, input().split())
grid=[list(map(int, input().split())) for _ in range(n)]
dy, dx=[-1, 0, 1, 0], [0, -1, 0, 1]
cctv=deepcopy(grid)
cctvs=[]
for i in range(n):
    for j in range(m):
        if 0<grid[i][j]<6:
            cctvs.append((i, j, grid[i][j]))
            cctv[i][j]=-1
def counting(cctv):
    cnt=0
    for i in range(n):
        for j in range(m):
            if grid[i][j]==0 and cctv[i][j]==0:
                cnt+=1
    return cnt
answer=sys.maxsize
def cctv1(y, x, d, tmp_cctvs):
    ny, nx=y+dy[d], x+dx[d]
    while 0<=ny<n and 0<=nx<m and grid[ny][nx]!=6:
        tmp_cctvs[ny][nx]=-1
        ny+=dy[d]
        nx+=dx[d]
def cctv2(y, x, d, tmp_cctvs):
    ny, nx=y+dy[d], x+dx[d]
    while 0<=ny<n and 0<=nx<m and grid[ny][nx]!=6:
        tmp_cctvs[ny][nx]=-1
        ny+=dy[d]
        nx+=dx[d]
    ny, nx=y-dy[d], x-dx[d]
    while 0<=ny<n and 0<=nx<m and grid[ny][nx]!=6:
        tmp_cctvs[ny][nx]=-1
        ny-=dy[d]
        nx-=dx[d]
def cctv3(y, x, d, tmp_cctvs):
    ny, nx=y+dy[d], x+dx[d]
    while 0<=ny<n and 0<=nx<m and grid[ny][nx]!=6:
        tmp_cctvs[ny][nx]=-1
        ny+=dy[d]
        nx+=dx[d]
    ny, nx = y+dy[(d+1)%4], x+dx[(d+1)%4]
    while 0<=ny<n and 0<=nx<m and grid[ny][nx]!=6:
        tmp_cctvs[ny][nx]=-1
        ny+=dy[(d+1)%4]
        nx+=dx[(d+1)%4]
def cctv4(y, x, d, tmp_cctvs):
    for i in range(4):
        if i == d:
            continue
        ny, nx=y+dy[i], x+dx[i]
        while 0<=ny<n and 0<=nx<m and grid[ny][nx]!=6:
            tmp_cctvs[ny][nx]=-1
            ny+=dy[i]
            nx+=dx[i]
def cctv5(y, x, tmp_cctvs):
    for i in range(4):
        ny, nx = y+dy[i], x+dx[i]
        while 0<=ny<n and 0<=nx<m and grid[ny][nx]!=6:
            tmp_cctvs[ny][nx]=-1
            ny+=dy[i]
            nx+=dx[i]
def setting(cctv, idx):
    global answer
    if idx==len(cctvs):
        answer=min(answer, counting(cctv))
        return
    if cctvs[idx][2]==1:
        for i in range(4):
            tmp_cctvs=deepcopy(cctv)
            cctv1(cctvs[idx][0], cctvs[idx][1], i, tmp_cctvs)
            setting(tmp_cctvs, idx+1)
    elif cctvs[idx][2]==2:
        for i in range(2):
            tmp_cctvs=deepcopy(cctv)
            cctv2(cctvs[idx][0], cctvs[idx][1], i, tmp_cctvs)
            setting(tmp_cctvs, idx+1)
    elif cctvs[idx][2]==3:
        for i in range(4):
            tmp_cctvs=deepcopy(cctv)
            cctv3(cctvs[idx][0], cctvs[idx][1], i, tmp_cctvs)
            setting(tmp_cctvs, idx+1)
    elif cctvs[idx][2]==4:
        for i in range(4):
            tmp_cctvs=deepcopy(cctv)
            cctv4(cctvs[idx][0], cctvs[idx][1], i, tmp_cctvs)
            setting(tmp_cctvs, idx+1)
    elif cctvs[idx][2]==5:
        tmp_cctvs=deepcopy(cctv)
        cctv5(cctvs[idx][0], cctvs[idx][1], tmp_cctvs)
        setting(tmp_cctvs, idx+1)
setting(cctv, 0)
print(answer)