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

https://pixabay.com/ko/photos/우산-햇빛-여자-비-빛-6239364/

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

15683번: 감시

 

해당 문제는 구현 문제입니다.

문제의 목표는 주어진 CCTV를 적절히 회전시켜서 사무실의 사각지대의 최소 크기를 구하는 것입니다.

 

CCTV의 종류는 총 5가지로, 각 종류마다 한 번에 감시 할 수 있는 방향이 다릅니다

 

CCTV의 종류 마다 감시할 수 있는 방향을 정의하는 방법이 해당 문제에서 중요한 포인트인 거 같습니다.

저는 아래 처럼 정의를 했습니다.

	dx, dy = (0, 1, 0, -1), (-1, 0, 1, 0)
	
    // 리스트 안의 각 숫자는 인덱스를 의미합니다.
	cctv_direction = {
        1: [[0], [1], [2], [3]],
        2: [[0, 2], [1, 3]],
        3: [[0, 1], [1, 2], [2, 3], [3, 0]],
        4: [[0, 1, 2], [1, 2, 3], [2, 3, 0], [3, 0, 1]],
        5: [[0, 1, 2, 3]]
    }

 

전체 코드

제출 언어: PyPy3

시간: 1388ms

 

from copy import deepcopy
import sys

def observe(cur_idx, cur_mat, cnt_blank):
    global cctv_list, cctv_direction, dy, dx, N, M, answer

    if cur_idx == len(cctv_list) or cnt_blank == 0:
        if answer > cnt_blank:
            answer = cnt_blank
        return

    cr, cc = cctv_list[cur_idx]
    cur_type = mat[cr][cc]

    for directions in cctv_direction[cur_type]:
        copied_cnt_blank = cnt_blank
        copied = deepcopy(cur_mat)

        for d in directions:
            cnt_change = 0
            if d == 0:
                for i in range(cr-1, -1, -1):
                    if copied[i][cc] == 0:
                        copied[i][cc] = -1
                        cnt_change += 1
                    
                    elif copied[i][cc] == 6:
                        break
                        
            elif d == 1:
                for j in range(cc+1, M):
                    if copied[cr][j] == 0:
                        copied[cr][j] = -1
                        cnt_change += 1
                    
                    elif copied[cr][j] == 6:
                        break
            
            elif d == 2:
                for i in range(cr+1, N):
                    if copied[i][cc] == 0:
                        copied[i][cc] = -1
                        cnt_change += 1

                    elif copied[i][cc] == 6:
                        break

            else:
                for j in range(cc-1, -1, -1):
                    if copied[cr][j] == 0:
                        copied[cr][j] = -1
                        cnt_change += 1
                    
                    elif copied[cr][j] == 6:
                        break
            
            copied_cnt_blank -= cnt_change

        observe(cur_idx+1, copied, copied_cnt_blank)


if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().strip().split())

    mat = [ list(map(int, sys.stdin.readline().strip().split())) for _ in range(N) ]

    max_blank = 0
    cctv_list = []

    for i in range(N):
        for j in range(M):
            if mat[i][j] == 0:
                max_blank += 1
            else:
                if mat[i][j] < 6:
                    cctv_list.append((i, j))

    answer = float('inf')

    dx, dy = (0, 1, 0, -1), (-1, 0, 1, 0)

    cctv_direction = {
        1: [[0], [1], [2], [3]],
        2: [[0, 2], [1, 3]],
        3: [[0, 1], [1, 2], [2, 3], [3, 0]],
        4: [[0, 1, 2], [1, 2, 3], [2, 3, 0], [3, 0, 1]],
        5: [[0, 1, 2, 3]]
    }

    if len(cctv_list) > 0:
        observe(0, mat, max_blank)
    else:
        answer = max_blank
    
    print(answer)

 

추가 정리

문제를 해결할때 CCTV의 방향이 정해지고 탐색하는 부분을 각 방향 별로 따로 구현을 했습니다.

기능적인 문제는 없지만 코드가 깔끔하지 않고 길어지는 아쉬움이 있습니다.

 

해당 부분을 아래처럼 구현하면 깔끔할 거 같습니다.

	...
    for directions in cctv_direction[cur_type]:
        copied_cnt_blank = cnt_blank
        copied = deepcopy(cur_mat)

        for d in directions:
            cnt_change = 0
            nr, nc = cr+dy[d], cc+dx[d]
            
            while 0 <= nr < N and 0 <= nc < M:
                if copied[nr][nc] == 0:
                    copied[nr][nc] = -1
                    cnt_change += 1
                
                elif copied[nr][nc] == 6:
                    break

                nr += dy[d]
                nc += dx[d]
            
            copied_cnt_blank -= cnt_change
	...

---

읽어 주셔서 감사합니다 :)

틀린 부분이 있다면 댓글로 편히 알려주세요😊