[파이썬] 백준 15683 : 감시 (골드4)

[파이썬] 백준 15683 : 감시 (골드4)

15683번: 감시

---

문제

---

풀이

0. 방향성 생각

• 카메라 기준 상하좌우 구하는 함수 check 작성
• 방향을 정했을 때 감시할 좌표를 반환하는 surveil 함수 작성
• 카메라가 많지 않아서 완탐 가능

1. 입력

from itertools import product
import sys
input = lambda : sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(h)]

 

2. Check 함수 정의

def check(x,y):
    global h,w    
    dire = {i:set() for i in range(4)}
    
    for i in range(y,-1,-1):
        if arr[i][x] == 6: break
        dire[0].add((x,i))
        
    for i in range(x,w):
        if arr[y][i] == 6: break
        dire[1].add((i,y))
        
    for i in range(y,h):
        if arr[i][x] == 6: break
        dire[2].add((x,i))
        
    for i in range(x,-1,-1):
        if arr[y][i] == 6: break
        dire[3].add((i,y))
        
    return dire

• 카메라를 중심으로 상하좌우 방향을 dire[방향] = set(좌표1,좌표2 ...)라고 정의한다.

 

3. surveil 함수 정의

def surveil(dire,n):
    surv = []

    if n==1:
        for i in range(4):
            surv.append(dire[i])

    elif n==2:
        for a,b in ((0,2),(1,3)):
            temp = set()
            temp.update(dire[a])
            temp.update(dire[b])
            surv.append(temp)

    elif n==3:
        for a,b in ((0,1),(1,2),(2,3),(3,0)):
            temp = set()
            temp.update(dire[a])
            temp.update(dire[b])
            surv.append(temp)

    elif n==4:
        for a,b,c in ((0,1,2),(1,2,3),(2,3,0),(3,0,1)):
            temp = set()
            temp.update(dire[a])
            temp.update(dire[b])
            temp.update(dire[c])
            surv.append(temp)

    else:
        temp = set()
        for i in range(4):
            temp.update(dire[i])
        surv.append(temp)

    return surv

• 카메라에 따라서 감시할 방향이 다르다.
• 카메라에 맞춰서 방향 선택하기.
• surv에다가 선택한 방향에 있는 모든 좌표들을 넣기

4. 탐색

camera = []
size = h*w
for i in range(h):
    for j in range(w):
        if 0<arr[i][j]<6:
            locs = check(j,i)
            camera.append(surveil(locs,arr[i][j]))
            
        elif arr[i][j] == 6:
            size -= 1

• 답 size는 기본적으로 h*w이고 여기서 벽의 개수 6을 빼야한다.
• 그 후 감시가능한 좌표수를 빼주면 정답
• camera가 위치한 곳에 check 함수, surveil 함수를 실행시킨다.
• camera에는 i번 카메라에 관한 좌표들이 선택한 방향에 따라 반환된다. ex) 2번 카메라 같은 경우 상하, 좌우 두 개 반환

5. 출력

def max_surveil(array):
    locs = []
    for comb in product(*array):
        temp = set()

        for c in comb:
            temp.update(c)
        locs.append(len(temp))

    return max(locs)

print(size-max_surveil(camera))

• 가능한 모든 경우 중 집합의 크기가 가장 큰 케이스를 찾고 size에서 빼준다.
• 모든 경우의 수는 product로 구함.
• 최대 경우의 수는  4**8 < 10**6이라 금방 완탐가능

 

---

전체코드

from itertools import product
import sys
input = lambda : sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(h)]

def check(x,y):
    global h,w    
    dire = {i:set() for i in range(4)}
    
    for i in range(y,-1,-1):
        if arr[i][x] == 6: break
        dire[0].add((x,i))
        
    for i in range(x,w):
        if arr[y][i] == 6: break
        dire[1].add((i,y))
        
    for i in range(y,h):
        if arr[i][x] == 6: break
        dire[2].add((x,i))
        
    for i in range(x,-1,-1):
        if arr[y][i] == 6: break
        dire[3].add((i,y))
        
    return dire

def surveil(dire,n):
    surv = []

    if n==1:
        for i in range(4):
            surv.append(dire[i])

    elif n==2:
        for a,b in ((0,2),(1,3)):
            temp = set()
            temp.update(dire[a])
            temp.update(dire[b])
            surv.append(temp)

    elif n==3:
        for a,b in ((0,1),(1,2),(2,3),(3,0)):
            temp = set()
            temp.update(dire[a])
            temp.update(dire[b])
            surv.append(temp)

    elif n==4:
        for a,b,c in ((0,1,2),(1,2,3),(2,3,0),(3,0,1)):
            temp = set()
            temp.update(dire[a])
            temp.update(dire[b])
            temp.update(dire[c])
            surv.append(temp)

    else:
        temp = set()
        for i in range(4):
            temp.update(dire[i])
        surv.append(temp)

    return surv

camera = []
size = h*w
for i in range(h):
    for j in range(w):
        if 0<arr[i][j]<6:
            locs = check(j,i)
            camera.append(surveil(locs,arr[i][j]))
            
        elif arr[i][j] == 6:
            size -= 1

def max_surveil(array):
    locs = []
    for comb in product(*array):
        temp = set()

        for c in comb:
            temp.update(c)
        locs.append(len(temp))

    return max(locs)

print(size-max_surveil(camera))

 

코멘트

카메라를 중심으로 주변탐색해야되는데 양 끝값부터 세다가 틀렸..

밥 먹으면서 쓱 봤는데 금방 찾아서 기분 굿