[백준 15683] 감시

1. 문제

www.acmicpc.net/problem/15683

15683번: 감시

2. 접근 방법

visited를 불리언 값을 갖는 2차 리스트로 만들어줘서, 감시 불가능한 위치의 value를 False로, 그 외에 나머지 것 (감시 가능한 위치, 벽, cctv)는 모두 True로 만들어준다.

사실 visited 안해줘도 되는데 탐색 없이 바로 답을 도출하고자 바로바로 cnt를 갱신하기 위해 visited를 만들어준 것 !

 

1. cctv의 위치를 리스트에 담아준다. (5는 그냥 만들면서 체크까지 해버림)

2. solve함수로 고고

2-1. 만약 ans(사각지대의 갯수)가 0이 되면 -> 더 이상 로직을 진행할 필요가 없기 때문에 바로 return해준다 (백트래킹)

2-2. 만약 cctv를 모두 설치했다면 (cctv 갯수만큼 로직을 진행했다면), ans와 현재 cnt(현재 사각지대 갯수)를 비교해서 더 작은 값으로 ans를 갱신해준다.

2-3. 아직 설치해야할 cctv가 남았다면, 상, 하, 좌, 우의 방향으로 cctv 방향을 만들어본다.

2-4. 이 때, for문을 사용해 다음 방향으로 넘어갈 때 visited를 다시 초기화 해줘야하므로, deep copy를 이용해 만든 temp_visited를 이용해 visited를 초기화해준다.

3. 이렇게 하고 ans를 print하면 끝~!

3. 코드

python

def isBoard(x, y):
    if x < 0 or x >= M or y < 0 or y >= N or board[y][x] == 6:
        return False
    return True

def watch(x, y, k):
    cnt = 0
    x, y = x+dx[k], y+dy[k]
    while isBoard(x, y):
        if not visited[y][x]:
            visited[y][x] = True
            cnt += 1
        x, y = x + dx[k], y + dy[k]
    return cnt

def cctv(x, y, type, k):
    cnt = 0
    if type == 1:
        cnt += watch(x, y, k)
    elif type == 2:
        cnt += watch(x, y, k)
        cnt += watch(x, y, (k+2)%4)
    elif type == 3:
        cnt += watch(x, y, k)
        cnt += watch(x, y, (k+1)%4)
    elif type == 4:
        cnt += watch(x, y, k)
        cnt += watch(x, y, (k+1)%4)
        cnt += watch(x, y, (k+2)%4)
    elif type == 5:
        for k in range(4):
            cnt += watch(x, y, k)
    return cnt

def solve(n, cnt):
    global ans, visited
    if ans == 0:
        return

    if n == len(cctv_lst):
        ans = min(ans, cnt)

    else:
        cx, cy, ct = cctv_lst[n]
        temp_visited = [visited[i][:] for i in range(N)]
        for k in range(4):
            solve(n+1, cnt-cctv(cx, cy, ct, k))
            visited = [temp_visited[i][:] for i in range(N)]

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
cctv_lst = []
visited = [[False]*M for _ in range(N)]
ans = N*M
dx, dy = (-1, 0, 1, 0), (0, 1, 0, -1)

for y in range(N):
    for x in range(M):
        if board[y][x] == 5:
            if not visited[y][x]:
                visited[y][x] = True
                ans -= 1
            ans -= cctv(x, y, 5, 0)
        elif board[y][x] == 6:
            visited[y][x] = True
            ans -= 1
        elif board[y][x] != 0 and board[y][x] != 6:
            cctv_lst.append([x, y, board[y][x]])
            if not visited[y][x]:
                visited[y][x] = True
                ans -= 1

solve(0, ans)
print(ans)

4. 마치며

문제 보자마자 가로 세로 8 이하여서 완탐이라고 생각했고 ,,

각 cctv마다 방향을 설정해줘야하니 재귀로 깊게 들어가야한다고 생각했다 ,,

그리고 메모는 이정도만 하고 문제 풀이에 들어갔더니 ^^,,

이렇게만 짜고 넘어갔더니 ^^

다 구현하고 보니 매우 그리디했다.

그리고 모든 예제도 통과하고 숨은 테케들도 모두 통과하길래 제출을 했는데,

7633B ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

였다. 

그래서 어디가 잘못되었는지 ^^

하나씩 확인하다가

내 코드에 내가 지쳐서 디버깅 포기

 

그리고 어디서 문제였는지

"파란피가 흐른다" 팀원에게 물어봤다.

 

접근 방법은 모두 동일했지만

나는 모듈화를 시키지 않아서 ^^

그냥 포기했다.

 

갓림이 만든 모듈화된 코드를 바탕으로

다시 사부작사부작 짜봤다.

 

더더 많이 풀어서 ㅠ 더욱 알고리즘하게 풀어야지,,