[백준] 15683 - 감시 (G5)

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

15683번: 감시

시뮬레이션, 구현, 브루트포스 유형의 문제이다.

생각보다 구현이 빡빡하다.

(체감 난이도 골드4)

 

이 문제를 풀 때 내가 실수했던 부분은 하나였다.

감시구역이 겹치는 점을 고려하지 못한 것이다.

그래서 백트래킹으로 감시구역을 바꿀때, 다른 CCTV에 의해서도 감시되는 구역에 대해 감시를 풀어버린 것 때문에 틀렸었다.

 

그래서 숫자를 이용해 감시 카운트를 세도록 했다.

감시가 생길때마다 숫자를 1씩 빼서 음수면 감시중, 0이면 감시 없음, 양수면 CCTV 이런식으로 활용했다.

(예시에서 #을 이용해서 이걸 그대로 활용한게 화근이었다)

 

CCTV 종류마다 감시구역이 바뀌는데, 공통적으로 각 방향에 대해 한줄을 통으로 감시한다.

이 부분을 함수로 빼서 구현하고, 각각의 방향에 대해 함수를 실행하는 식으로 구현하면 좀 편하게 구현할 수 있다.

(그래도 빡구현은 맞다)

 

def countHole():
    global n, m
    count = 0
    for i in range(n):
        for j in range(m):
            if board[i][j] == 0:
                count += 1

    return count

def setOneDirOfCCTV(_cctv, dir, isOn):
    global n, m
    if isOn:
        setValue = -1
    else:
        setValue = 1

    _x, _y = _cctv
    for k in range(1, MAX_SIZE): # 선택한 방향으로 1칸씩 이동하면서 설정
        if _x + dx[dir]*k < 0 or _x + dx[dir]*k == n or _y + dy[dir]*k < 0 or _y + dy[dir]*k == m: # 더 못가면 종료
            break
        if board[_x + dx[dir]*k][_y + dy[dir]*k] == 6: # 벽 만나면 종료
            break
        if 1 <= board[_x + dx[dir]*k][_y + dy[dir]*k] <= 5:
            continue
        board[_x + dx[dir]*k][_y + dy[dir]*k] += setValue

def kindOfCCTV(_cctv):
    return cctv[_cctv][0]

def setCCTV(_cctv, startDir, isOn): # 기준 방향을 받아서 해당 방향을 기준으로 CCTV 세팅
    _kind = kindOfCCTV(_cctv)
    if _kind == 1:
        setOneDirOfCCTV(_cctv, startDir, isOn)
    elif _kind == 2:
        setOneDirOfCCTV(_cctv, startDir, isOn)
        setOneDirOfCCTV(_cctv, (startDir + 2)%4, isOn)
    elif _kind == 3:
        setOneDirOfCCTV(_cctv, startDir, isOn)
        setOneDirOfCCTV(_cctv, (startDir+1)%4, isOn)
    elif _kind == 4:
        setOneDirOfCCTV(_cctv, startDir, isOn)
        setOneDirOfCCTV(_cctv, (startDir+1)%4, isOn)
        setOneDirOfCCTV(_cctv, (startDir+2)%4, isOn)
    elif _kind == 5:
        setOneDirOfCCTV(_cctv, startDir, isOn)
        setOneDirOfCCTV(_cctv, (startDir + 1) % 4, isOn)
        setOneDirOfCCTV(_cctv, (startDir + 2) % 4, isOn)
        setOneDirOfCCTV(_cctv, (startDir + 3) % 4, isOn)


def DFS(now_cctv_index):
    global answer
    now_cctv = sorted(cctv.keys())[now_cctv_index]
    _kind = kindOfCCTV(now_cctv)
    if _kind == 2:
        for _dir in range(2):
            setCCTV(now_cctv, _dir, isOn=True)
            if now_cctv_index == len(cctv) - 1: # 마지막 CCTV 라면 세팅하고 개수세고, 최솟값 갱신한다음 원래대로 복구
                answer = min(answer, countHole())
            else:
                DFS(now_cctv_index + 1)
            setCCTV(now_cctv, _dir, isOn=False)
    elif _kind == 5:
        setCCTV(now_cctv, 0, isOn=True)
        if now_cctv_index == len(cctv) - 1: # 마지막 CCTV 라면 세팅하고 개수세고, 최솟값 갱신한다음 원래대로 복구
            answer = min(answer, countHole())
        else:
            DFS(now_cctv_index + 1)
        setCCTV(now_cctv, 0, isOn=False)
    else:
        for _dir in range(4):
            setCCTV(now_cctv, _dir, isOn=True)
            if now_cctv_index == len(cctv) - 1: # 마지막 CCTV 라면 세팅하고 개수세고, 최솟값 갱신한다음 원래대로 복구
                answer = min(answer, countHole())
            else:
                DFS(now_cctv_index + 1)
            setCCTV(now_cctv, _dir, isOn=False)

MAX_SIZE = 8
dx = [0,1,0,-1]
dy = [1,0,-1,0]

board = []
answer = 100
n, m = map(int, input().split())
for _ in range(n):
    board.append([*map(int, input().split())])

cctv = dict()
for i in range(n):
    for j in range(m):
        if 0 < board[i][j] < 6:
            cctv[(i, j)] = (board[i][j], 0)

if len(cctv) == 0:
    print(countHole())
else:
    DFS(0)
    print(answer)

 

보다보면 코드에 중복이 많고, 반복문으로 해결할 수 있는 부분도 보인다.

코드를 좀 더 간결하게 만들어보았다.

 

def countHole():
    global n, m
    count = 0
    for i in range(n):
        for j in range(m):
            if board[i][j] == 0:
                count += 1

    return count

def setOneDirOfCCTV(_cctv, dir, isOn):
    global n, m
    if isOn:
        setValue = -1
    else:
        setValue = 1

    _x, _y = _cctv
    for k in range(1, MAX_SIZE): # 선택한 방향으로 1칸씩 이동하면서 설정
        if _x + dx[dir]*k < 0 or _x + dx[dir]*k == n or _y + dy[dir]*k < 0 or _y + dy[dir]*k == m: # 더 못가면 종료
            break
        if board[_x + dx[dir]*k][_y + dy[dir]*k] == 6: # 벽 만나면 종료
            break
        if 1 <= board[_x + dx[dir]*k][_y + dy[dir]*k] <= 5: # CCTV는 무시
            continue
        board[_x + dx[dir]*k][_y + dy[dir]*k] += setValue   # 값 세팅 

def kindOfCCTV(_cctv):
    return cctv[_cctv][0]

def setCCTV(_cctv, startDir, isOn): # 기준 방향을 받아서 해당 방향을 기준으로 CCTV 세팅
    _kind = kindOfCCTV(_cctv)
    if _kind == 1:
        setOneDirOfCCTV(_cctv, startDir, isOn)
    elif _kind == 2:
        setOneDirOfCCTV(_cctv, startDir, isOn)
        setOneDirOfCCTV(_cctv, (startDir + 2)%4, isOn)
    else:
        for k in range(_kind-1):
            setOneDirOfCCTV(_cctv, (startDir + k) % 4, isOn)    

def DFS(now_cctv_index):
    global answer
    now_cctv = sorted(cctv.keys())[now_cctv_index]
    _kind = kindOfCCTV(now_cctv)
    for _dir in range(4):
        setCCTV(now_cctv, _dir, isOn=True)
        if now_cctv_index == len(cctv) - 1: # 마지막 CCTV 라면 세팅하고 개수세고, 최솟값 갱신한다음 원래대로 복구
            answer = min(answer, countHole())
        else:
            DFS(now_cctv_index + 1)
        setCCTV(now_cctv, _dir, isOn=False)

MAX_SIZE = 8
dx = [0,1,0,-1]
dy = [1,0,-1,0]

board = []
answer = 100
n, m = map(int, input().split())
for _ in range(n):
    board.append([*map(int, input().split())])

cctv = dict()
for i in range(n):
    for j in range(m):
        if 0 < board[i][j] < 6:
            cctv[(i, j)] = (board[i][j], 0)

if len(cctv) == 0:
    print(countHole())
else:
    DFS(0)
    print(answer)

 

시간상으로는 더 비효율적이게 됐다.

2번 CCTV, 5번 CCTV는 4방향 모두에 대해 반복할 필요가 없는데도 반복을 하고있기 때문이다.

하지만 코드상으로는 더 깔끔해지게 됐다.