백준 감시

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

15683번: 감시

---

2번의 "틀렸습니다" 결과를 보고 질문 게시판을 보면서 반례들을 시도 해보면서 풀려고 했는데 결국 못풀어서 다른 사람의 풀이를 참조했다.

오답2의 코드는 cctv 감시영역을 확장할 때 매번 가장 많이 확장한 방향을 선택해서 확장해 나간다. 계속 틀려서 반례를 찾아봤다. 질문 게시판의 대부분의 반례를 통과해서 답답하던 중 통과되지 않는 반례를 찾았다. 이 반례를 통해 dfs + 완전 탐색을 해야한다는 것을 깨달았다. 

8 5
6 6 0 0 6
6 6 6 2 0
0 6 6 4 0
0 6 3 0 6
0 0 0 5 0
0 0 6 6 0
0 0 6 0 4
0 6 6 6 0
output: 9
correct answer: 8

7 5
6 0 0 0 6
0 4 1 6 6
6 0 6 0 6
0 6 0 3 6
0 6 0 1 6
6 6 0 5 6
6 6 6 5 6
output: 4
correct answer: 3

7 7
6 0 0 0 0 0 6
0 6 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 4
1 0 0 0 0 6 0
0 0 6 3 0 2 0
output: 16
correct answer: 15

그래서 오답1의 코드에서 dfs를 구현했는데, visited = 1 을 하니까 완탐이 안되었다.

결국 다른 분의 풀이를 참고했다. 

• cctv의 위치를 배열에 저장해놓고 이 배열만 체크
• depth(현재 cctv의 index) 로 dfs 종료 조건 설정

---

정답코드

import sys
import copy
input = sys.stdin.readline

N, M = map(int, input().split())
room = []
cctvlocs = []

for i in range(N):
    inputArr = list(map(int, input().split()))
    room.append(inputArr)
    for j in range(M):
        if 1 <= inputArr[j] <= 5:
            cctvlocs.append((inputArr[j], i, j))
totalCctv = len(cctvlocs)    

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

right = 3
left = 2
up = 1
down = 0
answer = int(1e9)
answerRoom = copy.deepcopy(room)
cctvs = {
    1: [[right], [left], [up], [down]],
    2: [[right, left], [up, down]],
    3: [[up, right], [down, right], [left, down], [up, left]],
    4: [[up, right, left], [up, right,down], [down, right,left], [down, up,left]],
    5: [[up, right, left, down]]
}


def expandCCTV(x, y, dir, curRoom):
    nx = x + dx[dir]
    ny = y + dy[dir]
    cnt = 0
    while 0 <= nx < N and 0 <= ny < M:
        if curRoom[nx][ny] == 6:
            break
        elif curRoom[nx][ny] == 0:
            curRoom[nx][ny] = 7
            cnt+= 1
        nx += dx[dir]
        ny += dy[dir]
    return cnt
    

def dfs(depth, curRoom):
    global answer, answerRoom, totalCctv
    if depth == totalCctv:
        curCnt = countInvisible(curRoom)
        if curCnt < answer:
            answer = curCnt
            answerRoom = curRoom
        return
    cctvNum, i, j = cctvlocs[depth]
    directions = cctvs[cctvNum]
    for direction in directions:
        expandedRoom = copy.deepcopy(curRoom)
        for d in direction:
            expandCCTV(i, j, d, expandedRoom)
        dfs(depth+1,  expandedRoom)
                    
     
def countInvisible(curRoom):
    cnt = 0
    for i in range(N):
        for j in range(M):
            if curRoom[i][j] == 0:  
                cnt += 1
    return cnt
                
    
def solve(curRoom):
    global answer, answerRoom
    dfs(0,curRoom)
    print(answer)
    # for r in answerRoom:
    #     print(r)
    return answer

solve(room)

참고 풀이: https://yeon-code.tistory.com/76

 

---

오답 코드 1

import sys
import copy
input = sys.stdin.readline

N, M = map(int, input().split())
room = []

for _ in range(N):
    room.append(list(map(int, input().split())))

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

right = 3
left = 2
up = 1
down = 0
answer = int(1e9)

cctvs = {
    1: [[right], [left], [up], [down]],
    2: [[right, left], [up, down]],
    3: [[up, right], [down, right], [left, down], [up, left]],
    4: [[up, right, left], [up, right,down], [down, right,left], [down, up,left]],
    5: [[up, right, left, down]]
}

def expandCCTV(x, y, dir, curRoom):
    nx = x + dx[dir]
    ny = y + dy[dir]
    cnt = 0
    while 0 <= nx < N and 0 <= ny < M:
        if curRoom[nx][ny] == 6:
            break
        elif curRoom[nx][ny] == 0:
            curRoom[nx][ny] = 7
            cnt+= 1
        nx += dx[dir]
        ny += dy[dir]
    return cnt
    

def dfs(curRoom, visited):
    global answer
    answer = min(answer, countInvisible(curRoom))
    for i in range(N):
        for j in range(M):
            if 1 <= curRoom[i][j] <= 5 and visited[i][j] == 0:
                visited[i][j] = 1
                directions = cctvs[curRoom[i][j]]
                for direction in directions:
                    expandedRoom = copy.deepcopy(curRoom)
                    for d in direction:
                        expandCCTV(i, j, d, expandedRoom)
                    dfs(expandedRoom, visited)

     
def countInvisible(curRoom):
    cnt = 0
    for i in range(N):
        for j in range(M):
            if curRoom[i][j] == 0:  
                cnt += 1
    return cnt
                
    
def solve(curRoom):
    visited = [[0 for _ in range(M)] for _ in range(N)]
    dfs(curRoom, visited)
    print(answer)
    return answer

solve(room)

 

 

---

오답 코드 2

import sys
import copy
input = sys.stdin.readline

N, M = map(int, input().split())
room = []

for _ in range(N):
    room.append(list(map(int, input().split())))

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

# right = (dx[3], dy[3])
# left = (dx[1], dy[1])
# up = (dx[2], dy[2])
# down = (dx[0], dy[0])
right = 3
left = 2
up = 1
down = 0

cctvs = {
    1: [[right], [left], [up], [down]],
    2: [[right, left], [up, down]],
    3: [[up, right], [down, right], [left, down], [up, left]],
    4: [[up, right, left], [up, right,down], [down, right,left], [down, up,left]],
    5: [[up, right, left, down]]
}

def expandCCTV(x, y, dir, curRoom):
    nx = x + dx[dir]
    ny = y + dy[dir]
    cnt = 0
    while 0 <= nx < N and 0 <= ny < M:
        if curRoom[nx][ny] == 6:
            break
        elif curRoom[nx][ny] == 0:
            curRoom[nx][ny] = 7
            cnt+= 1
        nx += dx[dir]
        ny += dy[dir]
    return cnt
    
def backTrack(cctv, x, y, curRoom):
    directions = cctvs[cctv]
    maxExpand = 0
    maxExpandedRoom = copy.deepcopy(curRoom)
    for direction in directions:
        expandedRoom = copy.deepcopy(curRoom)
        expandCnt= 0
        for d in direction:
            expandCnt += expandCCTV( x, y, d, expandedRoom)
        if expandCnt > maxExpand:
            maxExpand = expandCnt
            maxExpandedRoom = copy.deepcopy(expandedRoom)
    return maxExpandedRoom      
     
def countInvisible(curRoom):
    cnt = 0
    for i in range(N):
        for j in range(M):
            if curRoom[i][j] == 0:  
                cnt += 1
    return cnt
                
    
def solve(curRoom):
    for i in range(N):
        for j in range(M):
            if 1 <= curRoom[i][j] <= 5:
                curRoom = backTrack(curRoom[i][j], i, j, curRoom)
    answer = countInvisible(curRoom)
    print(answer)
    return answer

solve(room)