[DFS] 백준#15683: 감시/Python

📝 문제

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

15683번: 감시

💡 접근법

DFS 알고리즘을 활용하여 문제를 해결하였습니다. 문제 풀이는 다음과 같이 크게 세 부분으로 나눌 수 있습니다.

• 첫째, DFS 알고리즘을 활용하여 CCTV 종류별, 방향 전환에 따른 새로운 감시영역을 재귀적으로 탐색하는 함수
• 둘째, 특정 방향을 바라보는 CCTV의 최대 감시영역을 찾는 함수
• 셋째, 모든 CCTV에 대해 탐색이 끝나면 사각지대의 최솟값을 구하는 함수

CCTV 종류에 따라 감시할 수 있는 범위와 회전 가능한 방향이 다르기 때문에, 모든 경우의 수를 확인하기 위해 재귀 함수를 활용한 DFS를 사용하였습니다.

💻 코드

1) 전체 코드

import sys; input = sys.stdin.readline
import copy

# CCTV 종류별, 바라보는 방향별 감시영역 재귀적 탐색
def dfs(graph, depth):
    global answer
    # 종료 조건: 모든 CCTV 탐색
    if depth == len(cctv_list):
        # 사각지대 최솟값
        answer = min(answer, count_zero(graph))
        return
    else:
        # 사무실 정보 깊은 복사
        graph_copy = copy.deepcopy(graph)
        x, y, cctv_type = cctv_list[depth]
        for cctv_dir in cctv_direction[cctv_type]:
            # CCTV 감시영역 구하는 함수 호출
            watch(x, y, cctv_dir, graph_copy)
            # 현재 Case에서 타 모든 CCTV 재귀적 탐색
            dfs(graph_copy, depth + 1)
            # CCTV를 다른 방향으로 회전시킨 후 재탐색하기 위함
            graph_copy = copy.deepcopy(graph)

# CCTV 감시영역 구하는 함수
def watch(x, y, direction, graph):
    for d in direction:
        nx, ny = x, y
        # 특정 방향으로 벽을 만나거나 사무실을 벗어나기 전까지 탐색
        while True:
            nx += direction_list[d][0]
            ny += direction_list[d][1]
            # 맵 내 위치
            if 0 <= nx < N and 0 <= ny < M:
                # 벽을 만난 경우
                if graph[nx][ny] == 6:
                    break
                # 새로운 감시가능 영역일 경우
                elif graph[nx][ny] == 0:
                    graph[nx][ny] = '#'
            # 맵 외 위치
            else:
                break

# 사각지대 개수 구하는 함수
def count_zero(graph):
    cnt = 0
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 0:
                cnt += 1
    return cnt

if __name__ == '__main__':
    N, M = map(int, input().split())
    graph = [list(map(int, input().split())) for _ in range(N)]
    # 최솟값을 구하기 위해 초기값 10억 세팅
    answer = int(1e9)
    cctv_list = []
    for i in range(N):
        for j in range(M):
            if 1 <= graph[i][j] <= 5:
                # CCTV 좌표 및 종류 저장
                cctv_list.append((i, j, graph[i][j]))
    # 탐색 방향: 상, 하, 좌, 우
    direction_list = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    # CCTV별 이동 가능한 방향
    cctv_direction = [
        [],
        [[0], [1], [2], [3]], # 1번 CCTV
        [[0, 1], [2, 3]], # 2번 CCTV
        [[0, 2], [0, 3], [1, 2], [1, 3]], # 3번 CCTV
        [[0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3]], # 4번 CCTV
        [[0, 1, 2, 3]] # 5번 CCTV
    ]
    dfs(graph, 0)
    print(answer)

2) 해설

(1) 라이브러리 import

import sys; input = sys.stdin.readline
import copy

• sys 모듈
  • 파이썬 내장 함수인 input보다 빠르게 값을 입력받기 위해 sys.stdin.readline을 사용하였습니다.
• copy 모듈
  • copy는 Deep Copy라는 메서드를 사용하기 위한 모듈로, deepcopy() 메서드는 복사된 데이터를 변경해도 원본 데이터가 변경을 방지
  • 사무실 정보를 깊은 복사(Deep Copy)하여 CCTV를 회전하여 사각지대를 최소화할 수 있는 경우를 찾기 위해 사용

(2) DFS 알고리즘

# CCTV 종류별, 바라보는 방향별 감시영역 재귀적 탐색
def dfs(graph, depth):
    global answer
    # 종료 조건: 모든 CCTV 탐색
    if depth == len(cctv_list):
        # 사각지대 최솟값
        answer = min(answer, count_zero(graph))
        return
    else:
        # 사무실 정보 깊은 복사
        graph_copy = copy.deepcopy(graph)
        x, y, cctv_type = cctv_list[depth]
        for cctv_dir in cctv_direction[cctv_type]:
            # CCTV 감시영역 구하는 함수 호출
            watch(x, y, cctv_dir, graph_copy)
            # 현재 Case에서 타 모든 CCTV 재귀적 탐색
            dfs(graph_copy, depth + 1)
            # CCTV를 다른 방향으로 회전시킨 후 재탐색하기 위함
            graph_copy = copy.deepcopy(graph)

• 4~8번째 라인
  • 재귀 종료 조건: 모든 CCTV 탐색을 완료한 경우
  • 사각지대 개수의 최솟값을 구하는 함수를 호출하여 정답 산출
• 13~19번째 라인
  • CCTV별로 회전 가능한 방향에 따라 감시영역 산출

(3) CCTV 감시영역 구하는 함수

def watch(x, y, direction, graph):
    for d in direction:
        nx, ny = x, y
        # 특정 방향으로 벽을 만나거나 사무실을 벗어나기 전까지 탐색
        while True:
            nx += direction_list[d][0]
            ny += direction_list[d][1]
            # 맵 내 위치
            if 0 <= nx < N and 0 <= ny < M:
                # 벽을 만난 경우
                if graph[nx][ny] == 6:
                    break
                # 새로운 감시가능 영역일 경우
                elif graph[nx][ny] == 0:
                    graph[nx][ny] = '#'
            # 맵 외 위치
            else:
                break

CCTV 종류별로 회전에 따라 감시할 수 있는 영역이 다릅니다. 이 함수는 CCTV 종류별로 회전 가능한 모든 경우에서 감시 가능한 영역을 구합니다.

(4) 사각지대 개수 구하는 함수

def count_zero(graph):
    cnt = 0
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 0:
                cnt += 1
    return cnt

모든 CCTV 탐색 후 사각지대의 개수를 구하는 함수입니다.

(5) 메인함수

if __name__ == '__main__':
    N, M = map(int, input().split())
    graph = [list(map(int, input().split())) for _ in range(N)]
    # 최솟값을 구하기 위해 초기값 10억 세팅
    answer = int(1e9)
    cctv_list = []
    for i in range(N):
        for j in range(M):
            if 1 <= graph[i][j] <= 5:
                # CCTV 좌표 및 종류 저장
                cctv_list.append((i, j, graph[i][j]))
    # 탐색 방향: 상, 하, 좌, 우
    direction_list = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    # CCTV별 이동 가능한 방향
    cctv_direction = [
        [],
        [[0], [1], [2], [3]], # 1번 CCTV
        [[0, 1], [2, 3]], # 2번 CCTV
        [[0, 2], [0, 3], [1, 2], [1, 3]], # 3번 CCTV
        [[0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3]], # 4번 CCTV
        [[0, 1, 2, 3]] # 5번 CCTV
    ]
    dfs(graph, 0)
    print(answer)

메인 함수입니다. CCTV 종류마다 회전 가능한 방향을 cctv_direction 리스트에 저장하였습니다. 해당 번호는 탐색 가능한 방향(상, 하, 좌, 우)을 결정합니다.

✅ 채점 결과

채점 결과

PyPy3와 Python3 모두에서 패스했습니다. 반복문과 같은 복잡한 연산이 많다보니 PyPy3가 Python3보다는 시간 복잡도에서 우세하네요.

💾 Github

https://github.com/park-gb/algorithm-problem-solving/blob/main/dfs-bfs/boj_15683.py

GitHub - park-gb/algorithm-problem-solving: 알고리즘 문제 풀이 및 정리

📚 참고할 만한 포스팅

문제 풀이에 사용한 DFS 알고리즘에 대한 자세한 설명은 아래 포스팅을 참고해 주세요.

https://heytech.tistory.com/55

[알고리즘] 깊이 우선 탐색(DFS) 알고리즘에 대해 알아보자!(+Python 구현)

---

포스팅 내용에 오류가 있거나 접근법 및 코드 관련 피드백 환영합니다!😄
아래에 👇👇👇 댓글 남겨주시면 감사드리겠습니다.
그럼 오늘도 즐겁고 건강한 하루 보내시길 바랍니다 :)
고맙습니다.