[백준] 15683번: 감시 - python

문제 출처

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

15683번: 감시

 

 

 

 

---

 

풀이 & 코드

 

필자는 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)

 

 

 

 

전체 코드는 다음과 같다. 

 

 

 

 

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