[백준] 15683 - 감시 [Python(파이썬)]

'삼성 SW 역량 테스트' 기출 문제 입니다. 😀
문제 👉 15683번: 감시

1. 문제

1. N*M 보드에서 빈 칸(0), CCTV(1~5), 벽(6) 존재한다.
2. CCTV는 5개 존재한다.
   • 1번 한 방향
   • 2번 두 방향(반대)
   • 3번 두 방향(직각)
   • 4번 세 방향
   • 5번 네 방향
3. CCTV는 CCTV를 통과할 수 있다.
4. CCTV로 감시할 수 없는 사각 지대의 최소 크기를 출력한다. -> 최대 감시 구역 찾기

2. 풀이

브루트포스를 이용한 문제 풀이

1. CCTV가 가르킬 수 있는 모든 방향을 Dictionary에 저장한다.
2. 초기 빈칸의 개수와 CCTV의 위치와 종류를 배열에 저장한다.
3. CCTV가 감시하는 함수를 만든다.
   1. 감시는 상,하,좌,우 네 방향을 고려한다.
   2. CCTV가 감시할 때, 빈 칸이거나 CCTV라면 다음 칸으로 넘어간다.
   3. 벽이라면 감시를 중단한다.

3. 코드

N, M = map(int, input().split())
B = [list(map(int, input().split())) for _ in range(N)]
D = { # 상하좌우
    1:[(1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1)],
    2:[(1,1,0,0), (0,0,1,1)],
    3:[(1,0,1,0), (1,0,0,1), (0,1,1,0), (0,1,0,1)],
    4:[(1,1,1,0), (1,1,0,1), (1,0,1,1), (0,1,1,1)],
    5:[(1,1,1,1)]
}
mn = float('inf')
empty = 0
def solution():
    global mn, empty
    cctv = []
    for i in range(N):
        for j in range(M):
            if B[i][j] == 0:
                empty += 1
            if B[i][j]%6 != 0:
                cctv.append((i,j,B[i][j]))
    if not cctv : 
        return empty

    def observe(x,y,u,d,l,r):
        arr = set()
        if u:
            nx = x
            while nx-1 >= 0:
                if B[nx-1][y] == 0:
                    arr.add((nx-1,y))
                    nx -= 1
                elif B[nx-1][y] != 6:
                    nx -= 1
                else:
                    break
        if d:
            nx = x
            while nx+1 < N:
                if B[nx+1][y] == 0:
                    arr.add((nx+1,y))
                    nx += 1
                elif B[nx+1][y] != 6:
                    nx += 1
                else:
                    break
        if l:
            ny = y
            while ny-1 >= 0:
                if B[x][ny-1] == 0:
                    arr.add((x,ny-1))
                    ny -= 1
                elif B[x][ny-1] != 6:
                    ny -= 1
                else:
                    break
        if r:
            ny = y
            while ny+1 < M:
                if B[x][ny+1] == 0:
                    arr.add((x,ny+1))
                    ny += 1
                elif B[x][ny+1] != 6:
                    ny += 1
                else:
                    break
        return arr

    def bp(idx, arr):
        global mn, empty
        if idx == len(cctv):
            mn = min(mn, empty-len(arr))
            return
        x, y, d = cctv[idx][0], cctv[idx][1], cctv[idx][2]
        for u,d,l,r in D[d]:
            arr2 = observe(x,y,u,d,l,r)
            bp(idx+1, arr|arr2)

    bp(0,set())
    return mn

print(solution())

• 결과 : 328 ms

---

References

•  

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋