백준 & 프로그래머스

[백준] 15683번: 감시 - python

hyukji 2022. 12. 24. 23:41

문제 출처

https://www.acmicpc.net/problem/15683

 

15683번: 감시

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감

www.acmicpc.net

 

 

 

 


 

풀이 & 코드

 

필자는 cctv의 감시 방향을 string으로 변환해 dictionary에 저장했다. 상우하좌 순으로 0123으로 바꾸어 저장했다. 예를 들어, 2번 카메라의 경우 한번에 상하(02) 혹은 우좌(13) 방향을 감시한다. 3번 카메라의 경우 상우(01), 우하(12), 하좌(23), 좌상(30)이다. 

dx = [0,1,0,-1]
dy = [-1,0,1,0]

dic = dict()
dic[1] = ["0","1","2","3"]
dic[2] = ["02","13"]
dic[3] = ["01","12","23","30"]
dic[4] = ["012","123","230","301"]
dic[5] = ["0123"]

 

 

 

또한 bfs와 deque를 이용한 완전탐색을 이용했다. 모든 칸을 돌면서 해당 칸이 cctv일 경우 cctv의 종류에 맞춰 감시구역을 업데이트 한 후에 사무실 데이터를 dq에 추가해주었다. 

dq = deque([room])
for y, row in enumerate(room):
    for x, el in enumerate(row):
        if el == 0 or el ==6:
            continue
        for _ in range(len(dq)):
            target = dq.popleft()
            for _str in dic[el]:
                _next = [arr[:] for arr in target]
                check(_next, y, x, _str)
                
                dq.append(_next)

 

 

 

 

전체 코드는 다음과 같다. 

 

from collections import deque
r, c = map(int, input().split())
room = [list(map(int, input().split())) for _ in range(r)]
# 상우하좌 순으로 저장
dx = [0,1,0,-1]
dy = [-1,0,1,0]
# cctv의 감시 방향을 str형태로 저장(상0, 우1, 하2, 좌3)
dic = dict()
dic[1] = ["0","1","2","3"]
dic[2] = ["02","13"]
dic[3] = ["01","12","23","30"]
dic[4] = ["012","123","230","301"]
dic[5] = ["0123"]
# y,x에 _str에 맞추어 감시영역 체크
def check(target, y, x, _str):
for d in _str:
d = int(d)
ny, nx = y + dy[d], x + dx[d]
while 0 <= nx < c and 0 <= ny < r:
if target[ny][nx] == 6:
break
elif target[ny][nx] == 0:
target[ny][nx] = "#"
ny, nx = ny + dy[d], nx + dx[d]
# bfs로 칸들을 확인하면서 dq에 추가
dq = deque([room])
for y, row in enumerate(room):
for x, el in enumerate(row):
if el == 0 or el ==6:
continue
for _ in range(len(dq)):
target = dq.popleft()
for _str in dic[el]:
_next = [arr[:] for arr in target]
check(_next, y, x, _str)
dq.append(_next)
# dq에서 사각지대를 계산해 작은 값으로 출력
answer = float("inf")
for target in dq:
cnt = 0
for row in target:
cnt += row.count(0)
answer = cnt if cnt < answer else answer
print(answer)
view raw 15683.py hosted with ❤ by GitHub

 

 

 

해당 문제는 삼성 기출 문제로 골드 4에 배치된 문제이다.