[백준][python]15683 감시

문제

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

소스코드

import sys
import itertools

if __name__ == "__main__":
    n, m = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(n)]

    cctv_cnt = 0
    cctv = []
    wall = 0
    for i in range(n):
        for j in range(m):
            if arr[i][j] > 0 and arr[i][j] < 6:
                cctv_cnt += 1
                cctv.append([i, j])
            if arr[i][j] == 6:
                wall += 1


    cctv_list = list(itertools.product([i for i in range(4)], repeat=cctv_cnt))

    dx = [0,0,-1,1]
    dy = [1,-1,0,0]
    direction = {
        1 : [[0],[3],[1],[2]],
        2 : [[0,1],[2,3],[0,1],[2,3]],
        3 : [[0,2],[0,3],[1,3],[1,2]],
        4 : [[0,1,2],[0,2,3],[0,1,3],[1,2,3]],
        5 : [0,1,2,3]
    }
    # 행 열
    # 오른쪽 (0,1) 0
    # 왼쪽 (0,-1) 1
    # 위쪽 (-1,0) 2
    # 아래쪽 (1,0) 3


    res = int(1e9)
    for cl in cctv_list:
        visited = [[0] * m for _ in range(n)]

        for i in range(cctv_cnt):
            cctv_num = arr[cctv[i][0]][cctv[i][1]]
            if cctv_num == 5:
                cctv_dir = direction[cctv_num]
            else:
                cctv_dir = direction[cctv_num][cl[i]]

            for d in cctv_dir:
                x = cctv[i][0]
                y = cctv[i][1]
                xx = dx[d]
                yy = dy[d]
                while 0 <= x + xx < n and 0 <= y + yy < m:
                    if arr[x + xx][y + yy] == 6:
                        break
                    x += xx
                    y += yy
                    if visited[x][y] == 0 and arr[x][y] == 0:
                        visited[x][y] = 1

        v_cnt = 0
        for h in range(n):
            v_cnt += visited[h].count(1)
        tmp_res = max(0, (n * m) - wall - v_cnt - cctv_cnt)
        res = min(res, tmp_res)

    print(res)

설명

완전탐색으로 cctv의 가능한 모든 방향을 중복순열로 체크해두고, 가능한 모든 경우를 다 확인하 후 가장 최소의 사각지대를 찾아준다.

cctv의 최대 갯수는 8개이기 때문에 완전탐색이 가능하다고 판단했다.

 

예를 들어 cctv가 3개면 (0,0,0), (0,0,1), (0,0,2) .... (3,3,2),(3,3,3) 각각 모든 방향 경우의 수를 체크해준다.

    for cl in cctv_list: #cctv 방향 리스트를 모두 탐색해준다. 위에서 찾은 cctv좌표와 cctv 방향을 1:1 매칭해서 탐색한다.
        visited = [[0] * m for _ in range(n)] #탐색한 부분 체크 해주는 함수

        for i in range(cctv_cnt):#현재 주어진 cctv를 하나씩 체크한다.
            cctv_num = arr[cctv[i][0]][cctv[i][1]] #현재 cctv의 유형이 뭔지 파악한다.
            if cctv_num == 5: #5인 경우는 따로 처리해준다. 이렇게 하지 않으려면 direction 딕셔너리에서 5의 값에 [0,1,2,3,4] 를 4번 넣어줘야한다.
                cctv_dir = direction[cctv_num]
            else:
                cctv_dir = direction[cctv_num][cl[i]] #현재 cctv유형이 어디 방향인지 정해준다.

            for d in cctv_dir: #탐색해야할 방향 탐색
                x = cctv[i][0] #cctv 현재 위치
                y = cctv[i][1]
                xx = dx[d] # 탐색해야할 방향
                yy = dy[d]
                while 0 <= x + xx < n and 0 <= y + yy < m: #범위 내에 있으면 계속 탐색
                    if arr[x + xx][y + yy] == 6: #벽이면 종료
                        break
                    x += xx #계속 탐색
                    y += yy
                    if visited[x][y] == 0 and arr[x][y] == 0: # 빈공간인 경우 cctv 중복 탐색이 가능하니까 탐색처리
                        visited[x][y] = 1

사각지대는 전체에서 벽 갯수 빼주고, cctv 갯수 빼주고, 탐색한 갯수 빼주면 된다.

- 가 나오는 경우가 있기 때문에 -인 경우 0 처리해준다.

 

후기

완전탐색과 개빡센 구현문제 

 

로직 완벽 구현 + 질문게시판에 있는 반례 다맞음 + tc 다맞았는데 계속 1%에서 틀렸다고 나오길래 자고 다시 풀어봤다

로직은 문제가 없어보였다.

방향을 잘못 설정해줬다. 이번엔 그림으로 그리면서 다시 설정했다. 눈으로 풀어서 실수했나보다ㅠ.ㅠ

    dx = [0,0,-1,1]
    dy = [1,-1,0,0]
    direction = {
        1 : [[0],[3],[1],[2]],
        2 : [[0,1],[2,3],[0,1],[2,3]],
        3 : [[0,2],[0,3],[1,3],[1,2]],
        4 : [[0,1,2],[0,2,3],[0,1,3],[1,2,3]],
        5 : [0,1,2,3]
    }