백준 / 감시 / 15683번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 감시 / 15683번 (골드 3단계)

문제 사이트: https://www.acmicpc.net/problem/15683

 

문제 설명

---

나의 풀이

# 깊은 복사
import copy

# CCTV별 감시 방향 정의 (상, 하, 좌, 우)
directions = {
    1: [[(0, 1)], [(0, -1)], [(1, 0)], [(-1, 0)]],  # 단방향
    2: [[(0, 1), (0, -1)], [(1, 0), (-1, 0)]],  # 양방향
    3: [[(-1, 0), (0, 1)], [(0, 1), (1, 0)], [(1, 0), (0, -1)], [(0, -1), (-1, 0)]],  # 직각 방향
    4: [[(-1, 0), (0, 1), (0, -1)], [(0, 1), (1, 0), (-1, 0)], [(1, 0), (0, -1), (0, 1)],
        [(0, -1), (-1, 0), (1, 0)]],  # 세 방향
    5: [[(0, 1), (0, -1), (1, 0), (-1, 0)]]  # 네 방향 모두
}


def move_search(cctv_number, simulation_case, n, m, position, direction_set):
    """CCTV 감시 영역을 표시"""
    y, x = position
    for dy, dx in direction_set:
        ny, nx = y, x
        while True:
            ny += dy
            nx += dx
            if 0 <= ny < n and 0 <= nx < m:
                if simulation_case[ny][nx] == 6:  # 벽
                    break
                if simulation_case[ny][nx] == 0:  # 감시 가능한 영역
                    simulation_case[ny][nx] = '#'
            else:  # 범위를 벗어나면 종료
                break

def dfs(depth, cctv_index, office, n, m, result):
    """DFS로 모든 CCTV 방향 조합 탐색"""
    if depth == len(cctv_index):  # 모든 CCTV를 처리한 경우
        # 사각지대 계산
        blind_spots = sum(row.count(0) for row in office)
        result[0] = min(result[0], blind_spots)
        return

    # 현재 CCTV 정보
    y, x = cctv_index[depth]
    cctv_number = office[y][x]

    # 모든 방향에 대해 시뮬레이션
    for direction_set in directions[cctv_number]:
        simulation = copy.deepcopy(office)
        move_search(cctv_number, simulation, n, m, (y, x), direction_set)
        dfs(depth + 1, cctv_index, simulation, n, m, result)


def cctv(offices, n, m):
    # CCTV 위치 저장
    cctv_index = []
    for i in range(n):
        for j in range(m):
            if offices[i][j] != 0 and offices[i][j] != 6:
                cctv_index.append((i, j))

    # 결과 초기화 (사각지대 최솟값)
    result = [float('inf')]
    dfs(0, cctv_index, offices, n, m, result)
    return result[0]


def main():
    # 입력 처리
    n, m = map(int, input().split())
    office = [list(map(int, input().split())) for _ in range(n)]

    # 사각지대 최소값 계산
    answer = cctv(office, n, m)
    print(answer)

main()

코드가 길어서 하나씩 설명하도록 하겠습니다!

 

아래의 코드는 CCTV 별로 감시하는 영역을 표시하는 코드 입니다.

# CCTV별 감시 방향 정의 (상, 하, 좌, 우)
directions = {
    1: [[(0, 1)], [(0, -1)], [(1, 0)], [(-1, 0)]],  # 단방향
    2: [[(0, 1), (0, -1)], [(1, 0), (-1, 0)]],  # 양방향
    3: [[(-1, 0), (0, 1)], [(0, 1), (1, 0)], [(1, 0), (0, -1)], [(0, -1), (-1, 0)]],  # 직각 방향
    4: [[(-1, 0), (0, 1), (0, -1)], [(0, 1), (1, 0), (-1, 0)], [(1, 0), (0, -1), (0, 1)],
        [(0, -1), (-1, 0), (1, 0)]],  # 세 방향
    5: [[(0, 1), (0, -1), (1, 0), (-1, 0)]]  # 네 방향 모두
}

 

cctv 함수

def cctv(offices, n, m):
    # CCTV 위치 저장
    cctv_index = []
    for i in range(n):
        for j in range(m):
            if offices[i][j] != 0 and offices[i][j] != 6:
                cctv_index.append((i, j))

    # 결과 초기화 (사각지대 최솟값)
    result = [float('inf')]
    dfs(0, cctv_index, offices, n, m, result)
    return result[0]

 

dfs 함수

모든 CCTV와 비교가 끝나면  blind_spots은 각 사무실 라인 별 0의 개수를 저장하고

result[0]과 비교하여 더 작은 최소 감시 영역을 저장합니다.

def dfs(depth, cctv_index, office, n, m, result):
    """DFS로 모든 CCTV 방향 조합 탐색"""
    if depth == len(cctv_index):  # 모든 CCTV를 처리한 경우
        # 사각지대 계산
        blind_spots = sum(row.count(0) for row in office)
        result[0] = min(result[0], blind_spots)
        return

    # 현재 CCTV 정보
    y, x = cctv_index[depth]
    cctv_number = office[y][x]

    # 모든 방향에 대해 시뮬레이션
    for direction_set in directions[cctv_number]:
        simulation = copy.deepcopy(office)
        move_search(cctv_number, simulation, n, m, (y, x), direction_set)
        dfs(depth + 1, cctv_index, simulation, n, m, result)

 

move_search 함수

모든 방향으로 탐색을 진행하고 벽을 만나게 되면 종료합니다.

def move_search(cctv_number, simulation_case, n, m, position, direction_set):
    """CCTV 감시 영역을 표시"""
    y, x = position
    for dy, dx in direction_set:
        ny, nx = y, x
        while True:
            ny += dy
            nx += dx
            if 0 <= ny < n and 0 <= nx < m:
                if simulation_case[ny][nx] == 6:  # 벽
                    break
                if simulation_case[ny][nx] == 0:  # 감시 가능한 영역
                    simulation_case[ny][nx] = '#'
            else:  # 범위를 벗어나면 종료
                break

---

※ 알아야 할 것

# 깊은 복사
import copy

# CCTV별 감시 방향 정의 (상, 하, 좌, 우)
directions = {
    1: [[(0, 1)], [(0, -1)], [(1, 0)], [(-1, 0)]],  # 단방향
    2: [[(0, 1), (0, -1)], [(1, 0), (-1, 0)]],  # 양방향
    3: [[(-1, 0), (0, 1)], [(0, 1), (1, 0)], [(1, 0), (0, -1)], [(0, -1), (-1, 0)]],  # 직각 방향
    4: [[(-1, 0), (0, 1), (0, -1)], [(0, 1), (1, 0), (-1, 0)], [(1, 0), (0, -1), (0, 1)], [(0, -1), (-1, 0), (1, 0)]],  # 세 방향
    5: [[(0, 1), (0, -1), (1, 0), (-1, 0)]]  # 네 방향 모두
}


def move_search(cctv_number, simulation_case, n, m, position, direction_set):
    """CCTV 감시 영역을 표시"""
    y, x = position
    for dy, dx in direction_set:
        ny, nx = y, x
        while True:
            ny += dy
            nx += dx
            if 0 <= ny < n and 0 <= nx < m:
                if simulation_case[ny][nx] == 6:  # 벽
                    break
                if simulation_case[ny][nx] == 0:  # 감시 가능한 영역
                    simulation_case[ny][nx] = '#'
            else:  # 범위를 벗어나면 종료
                break


def dfs(depth, cctv_index, office, n, m, result):
    """DFS로 모든 CCTV 방향 조합 탐색"""
    if depth == len(cctv_index):  # 모든 CCTV를 처리한 경우
        # 사각지대 계산
        blind_spots = sum(row.count(0) for row in office)
        result[0] = min(result[0], blind_spots)
        return

    # 현재 CCTV 정보
    y, x = cctv_index[depth]
    cctv_number = office[y][x]

    # 모든 방향에 대해 시뮬레이션
    for direction_set in directions[cctv_number]:
        simulation = copy.deepcopy(office)
        move_search(cctv_number, simulation, n, m, (y, x), direction_set)
        print(f"Simulating depth {depth}:")
        for row in simulation:
            print(row)
        print("\n")
        dfs(depth + 1, cctv_index, simulation, n, m, result)


def cctv(offices, n, m):
    # CCTV 위치 저장
    cctv_index = []
    for i in range(n):
        for j in range(m):
            if offices[i][j] != 0 and offices[i][j] != 6:
                cctv_index.append((i, j))

    # 결과 초기화 (사각지대 최솟값)
    result = [float('inf')]
    dfs(0, cctv_index, offices, n, m, result)
    return result[0]


def main():
    # 입력 처리
    n, m = map(int, input().split())
    office = [list(map(int, input().split())) for _ in range(n)]

    # 사각지대 최소값 계산
    answer = cctv(office, n, m)
    print(answer)

main()

직접 테스트 하고싶은 분은 위 코드를 사용하면 됩니다!