[맛있는물회] [파이썬] <백준 알고리즘> 15683번 "감시"

문제 조건

---

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

1번	2번	3번	4번	5번

1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.

CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.

CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.

0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 6 0 0 0 0 0 0 0

지도에서 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호이다. 위의 예시에서 1번의 방향에 따라 감시할 수 있는 영역을 '#'로 나타내면 아래와 같다.

→	←	↑	↓

CCTV는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때는 6의 오른쪽에 있는 벽을 감시할 수 없다.

0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 6 0 0 6 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 5

위의 예시에서 감시할 수 있는 방향을 알아보면 아래와 같다.

왼쪽 상단 2: ↔, 오른쪽 하단 2: ↔	왼쪽 상단 2: ↔, 오른쪽 하단 2: ↕	왼쪽 상단 2: ↕, 오른쪽 하단 2: ↔	왼쪽 상단 2: ↕, 오른쪽 하단 2: ↕

CCTV는 CCTV를 통과할 수 있다. 아래 예시를 보자.

0 0 2 0 3 0 6 0 0 0 0 0 6 6 0 0 0 0 0 0

위와 같은 경우에 2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.

# # 2 # 3 0 6 # 0 # 0 0 6 6 # 0 0 0 0 #

사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.

 

Input

---

첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다. 

CCTV의 최대 개수는 8개를 넘지 않는다.

 

Output

---

첫째 줄에 사각 지대의 최소 크기를 출력한다.

 

생각한 아이디어

---

하... 2시간걸렸다...

 

맨첨에 진짜 걍 브루트 포스로 구현했다가 코드가 350줄이 나왔다.

파이썬 쓰면서 이렇게 긴 코드는 첨이야... ★

계속 시간초과 뜨다가 조금만 고쳤더니 성공은 했다.

 

그리고 숏코딩 좀 보면서 젤빠른 파이썬 코드를 조금 보았더니

코드를 10%로 줄여놨다.. ㅎㅎ

 

그래서 조금 참고해서 수정하고 포스팅한다.

 

맨첨에 나도 CCTV마다 다른 리스트를 만들어보려고 했으나 로직이 생각이 안나서 못했다.

 

이 분은 

di = [0,

[[0],[1],[2],[3]],

[[0,1],[2,3]],

[[1,2],[1,3],[0,2],[0,3]],

[[0,1,2],[0,1,3],[0,2,3],[1,2,3]],

[[0,1,2,3]]]

이렇게 아주 우아하게 코드를 짜셨다.

 

각 CCTV마다 갈수있는 방향을 가진 리스트를 각각 만들어놓은 것이다.

그리고 파이썬답게 for 문을 

num,y,x = cctv[start]

   for dir in di[num]:

      tmp = copy.deepcopy(MAP)

      for i in dir:

         ny,nx=y+dy[i],x+dx[i]

         while 0<=ny<row and 0<=nx<col:

            if tmp[ny][nx]==6:

               break

            elif tmp[ny][nx]==0:

               tmp[ny][nx]='#'

            ny+=dy[i]

            nx+=dx[i]

      dfs(start+1,tmp,cctv)

 

이렇게 써주면 깔~~끔하게 구현이 된다..

 

나도 이제 코드를 짤때 너무 막 짜지말고, 좀더 심사숙고하고 짜는 습관을 들여야겠다 :)

 

 

 

소스코드

import sys
import math
from collections import deque
import copy
input=sys.stdin.readline
INF=sys.maxsize

dy=[-1,1,0,0]
dx=[0,0,-1,1]
di = [0,[[0],[1],[2],[3]],[[0,1],[2,3]],[[1,2],[1,3],[0,2],[0,3]],[[0,1,2],[0,1,3],[0,2,3],[1,2,3]],[[0,1,2,3]]]

MIN=9999999999999999
def dfs(start,MAP,cctv):
   global MIN
   if start==len(cctv):
      cnt=0
      for y in range(0,row):
         for x in range(0,col):
            if MAP[y][x]==0:
               cnt+=1
      MIN=min(MIN,cnt)
      return

   num,y,x = cctv[start]
   for dir in di[num]:
      tmp = copy.deepcopy(MAP)
      for i in dir:
         ny,nx=y+dy[i],x+dx[i]
         while row>ny>=0 and col>nx>=0:
            if tmp[ny][nx]==6:
               break
            elif tmp[ny][nx]==0:
               tmp[ny][nx]='#'
            ny+=dy[i]
            nx+=dx[i]
      dfs(start+1,tmp,cctv)
   
if __name__ == "__main__":
   row,col=map(int,input().split())
   MAP=[list(map(int,input().split())) for _ in range(row)]
   cctv=[]
   block_cnt=0
   for y in range(0,row):
      for x in range(0,col):
         if MAP[y][x] not in [0,6]:
            cctv.append([MAP[y][x],y,x])
         elif MAP[y][x]==6:
            block_cnt+=1
   dfs(0,MAP,cctv)
   print(MIN)

 

*파이썬 문법 정리