728x90
문제 링크
https://www.acmicpc.net/problem/15683
TIL
DFS(깊이 우선 탐색)를 활용하겠다고 생각하는 사고 과정
1️⃣ 문제의 핵심 파악
CCTV가 감시하는 방향을 설정하고, 최적의 감시 영역을 찾는 문제다.
✅ 주어진 정보
- 각 CCTV는 회전할 수 있으며, 유형별로 감시 가능한 방향이 다르다.
- 감시된 영역을 계산해서 **사각지대(0의 개수)**를 최소화해야 한다.
- CCTV가 최대 8개이므로 모든 경우를 탐색하는 완전 탐색(Brute-force)이 가능하다.
✅ 문제 유형 분석
- 모든 CCTV에 대해 감시 방향을 설정하는 모든 경우를 고려해야 한다.
- CCTV의 방향을 조합할 때 완전 탐색이 필요하다.
- 감시 범위를 적용한 후에는 다시 원래 상태로 되돌려야 한다.
- 이는 **"상태를 저장하고 복원하는 백트래킹(Backtracking) 기법"**이 필요함을 의미한다.
2️⃣ DFS를 사용하겠다고 판단하는 과정
💡 "DFS를 사용하면 모든 CCTV의 방향 조합을 효율적으로 탐색할 수 있을까?"
→ 답은 YES!
🚀 DFS 사용을 결정하는 주요 근거
- 모든 CCTV의 방향 조합을 고려해야 한다.
- 예를 들어, CCTV가 4개 있고, 각 CCTV가 4가지 방향을 선택할 수 있다면
→ 4^4 = 256가지의 경우를 탐색해야 함. - CCTV가 8개여도 4^8 = 65,536 정도라서 완전 탐색 가능.
- 예를 들어, CCTV가 4개 있고, 각 CCTV가 4가지 방향을 선택할 수 있다면
- 모든 CCTV의 조합을 고려하는 트리 구조를 생각할 수 있다.
- 트리 구조에서 각 CCTV의 방향을 하나씩 결정하면서 탐색을 진행하는 것이므로 DFS 방식이 적합하다.
- 한 CCTV의 방향을 정하면, 다음 CCTV 방향을 정하는 문제로 변환됨 → DFS로 해결 가능!
- DFS를 이용하면 "상태를 저장하고 복원하는 백트래킹"을 쉽게 구현 가능
- 특정 방향을 정하면 감시 영역을 표시하고,
- 다음 CCTV의 방향을 선택하며 재귀 호출(DFS 탐색)
- 모든 CCTV를 배치한 후, 최소 사각지대 계산
- 탐색을 마친 후, 원래 상태로 되돌리는 백트래킹 수행.
3️⃣ DFS를 어떻게 적용할지 구체적인 사고 과정
✔ DFS를 활용한 상태 트리 구성
1️⃣ CCTV를 순서대로 하나씩 처리한다.
2️⃣ 해당 CCTV의 가능한 모든 감시 방향을 하나씩 선택하여 DFS 탐색 진행
3️⃣ 감시 영역을 업데이트한 후 다음 CCTV 방향을 결정하는 DFS 호출
4️⃣ 모든 CCTV 방향을 설정한 후, 사각지대 최소값을 갱신
5️⃣ 되돌아가면서 원래 상태를 복원(백트래킹)
[ 원래 코드 ] - 완전 탐색 + 그리디
from itertools import combinations
n, m = map(int, input().split())
office = [list(map(int, input().split())) for _ in range(n)]
cctv = [] # cctv#, (y,x) >> sort(reverse=True) 정렬할 것:: 큰 cctv 순으로 정렬
for i in range(n):
for j in range(m):
if 0 < office[i][j] < 6:
cctv.append([office[i][j], (i,j)])
cctv.sort(reverse=True) # sort vs sorted reverse랑 매개변수 알아보기
def watch_n(num_cctv, coord):
cy, cx = coord[0], coord[1]
ny = cy-1
while 0<=ny: # 북
if 0<=ny and office[ny][cx] != 6:
office[ny][cx] = num_cctv
else:
break
ny -= 1
def watch_s(num_cctv, coord):
cy, cx = coord[0], coord[1]
ny = cy+1
while ny<n: # 남
if ny<n and office[ny][cx] != 6:
office[ny][cx] = num_cctv
else:
break
ny += 1
def watch_e(num_cctv, coord):
cy, cx = coord[0], coord[1]
nx = cx+1
while nx<m: # 동
if nx<m and office[cy][nx] != 6:
office[cy][nx] = num_cctv
else:
break
nx += 1
def watch_w(num_cctv, coord):
cy, cx = coord[0], coord[1]
nx = cx-1
while 0<=nx: # 서
if nx<m and office[cy][nx] != 6:
office[cy][nx] = num_cctv
else:
break
nx -= 1
def find_best(coord):
cy, cx = coord[0], coord[1]
ret = []
# 북, 동, 남, 서
ny = cy
cnt = 0
while True: # 북
ny -= 1
if 0<=ny and office[ny][cx] != 6:
if office[ny][cx] == 0:
cnt += 1
else:
break
ret.append((cnt,"N"))
nx = cx
cnt = 0
while True: # 동
nx += 1
if nx<m and office[cy][nx] != 6:
if office[cy][nx] == 0:
cnt += 1
else:
break
ret.append((cnt,"E"))
ny = cy
cnt = 0
while True: # 남
ny += 1
if ny<n and office[ny][cx] != 6:
if office[ny][cx] == 0:
cnt += 1
else:
break
ret.append((cnt,"S"))
nx = cx
cnt = 0
while True: # 서
nx -= 1
if 0<=nx and office[cy][nx] != 6:
if office[cy][nx] == 0:
cnt += 1
else:
break
ret.append((cnt,"W"))
return ret
# 5번 먼저 칠함
for c in cctv:
num_cctv, (cy, cx) = c # 리스트에 넣을 때, 튜플로 넣었기 때문에 () 안하면 값이 안받아짐 > cy,cx 그냥 하면 안됨
if num_cctv == 5:
watch_n(num_cctv, (cy,cx))
watch_s(num_cctv, (cy,cx))
watch_e(num_cctv, (cy,cx))
watch_w(num_cctv, (cy,cx))
elif num_cctv == 4:
zeros = find_best((cy, cx))
zeros.sort(reverse=True)
_, dir = zeros[-1]
if dir == "N":
watch_s(num_cctv, (cy,cx))
watch_e(num_cctv, (cy,cx))
watch_w(num_cctv, (cy,cx))
elif dir == "E":
watch_n(num_cctv, (cy,cx))
watch_s(num_cctv, (cy,cx))
watch_w(num_cctv, (cy,cx))
elif dir == "S":
watch_n(num_cctv, (cy,cx))
watch_e(num_cctv, (cy,cx))
watch_w(num_cctv, (cy,cx))
elif dir == "W":
watch_n(num_cctv, (cy,cx))
watch_s(num_cctv, (cy,cx))
watch_e(num_cctv, (cy,cx))
elif num_cctv == 3: # orthogonal
zeros = find_best((cy, cx))
# 시계 방향
candid = [(zeros[0][0]+zeros[1][0],"NE"), (zeros[1][0]+zeros[2][0],"ES"), (zeros[2][0]+zeros[3][0],"SW"), (zeros[3][0]+zeros[0][0],"WN")]
candid.sort(reverse=True)
if candid[0][1] == "NE":
watch_n(num_cctv, (cy,cx))
watch_e(num_cctv, (cy,cx))
elif candid[0][1] == "ES":
watch_e(num_cctv, (cy,cx))
watch_s(num_cctv, (cy,cx))
elif candid[0][1] == "SW":
watch_w(num_cctv, (cy,cx))
watch_s(num_cctv, (cy,cx))
elif candid[0][1] == "WN":
watch_w(num_cctv, (cy,cx))
watch_n(num_cctv, (cy,cx))
elif num_cctv == 2: # horizontal
zeros = find_best((cy, cx)) # 북, 동, 남, 서
if zeros[0][0]+zeros[2][0] >= zeros[1][0]+zeros[3][0]:
watch_n(num_cctv, (cy,cx))
watch_s(num_cctv, (cy,cx))
else:
watch_e(num_cctv, (cy,cx))
watch_w(num_cctv, (cy,cx))
elif num_cctv == 1:
zeros = find_best((cy, cx))
zeros.sort(reverse=True)
_, dir = zeros[0]
if dir == "N":
watch_n(num_cctv, (cy,cx))
elif dir == "E":
watch_e(num_cctv, (cy,cx))
elif dir == "S":
watch_s(num_cctv, (cy,cx))
elif dir == "W":
watch_w(num_cctv, (cy,cx))
answer = sum(row.count(0) for row in office)
print(answer)- 얼핏 보면 각 CCTV마다 가장 많이 감시할 수 있는 방향을 선택하면 될 것 같아서, 그리디(Greedy) 사용
❌ 그리디 접근: 왜 안 될까?
1. 그리디는 "지역 최적"만 보고 결정함
- 그리디 방식은 각 CCTV가 감시할 수 있는 영역을 "단독 기준"으로 최대화하는 방향을 선택하게 됩니다.
- 즉, CCTV 1번이 혼자 봤을 때 가장 많은 칸을 감시할 수 있는 방향을 택함
그런데... 다른 CCTV들이 그 영역을 이미 감시할 수 있는데도 중복으로 감시하게 될 수 있어요!
✔ 예시로 보면 명확해져요
📍 상황
- CCTV A는 → 방향으로 5칸 감시할 수 있음
- CCTV B는 ↓ 방향으로 3칸 감시할 수 있음
→ CCTV A가 → 방향을 선택한 경우,
→ B가 감시할 영역과 많이 겹쳐서 중복 감시가 발생할 수 있음
👉 결과적으로 전체 사각지대가 줄어들지 않음
(오히려 A가 ↓ 방향을 택했으면 덜 겹치고 사각지대가 더 줄었을 수도 있음)
2. 모든 CCTV의 "조합"을 고려해야 최적해 도출 가능
- 이 문제는 단순히 각 CCTV의 감시 최대화가 목적이 아니라,
"전체 사각지대 최소화"가 목표입니다.
✔ CCTV 간 감시 영역의 겹침/중복
✔ 벽으로 인해 감시가 막히는 방향
✔ 각 CCTV의 방향을 설정하는 순서와 조합
이러한 요소를 전부 고려해야 하므로, 단일 기준으로 결정하는 그리디는 오답을 만들 가능성이 큽니다.
✅ 왜 DFS(백트래킹)는 정답을 찾을 수 있을까?
- DFS는 모든 CCTV의 모든 방향 조합을 완전 탐색해서,
- CCTV들이 어떻게 협력해서 감시할 때 사각지대가 가장 적은지 전역 최적해를 찾습니다.
📌 탐색 순서:
→ CCTV 1의 방향 1 → CCTV 2의 방향 1 → CCTV 3의 방향 1
→ CCTV 1의 방향 1 → CCTV 2의 방향 1 → CCTV 3의 방향 2
... 이런 식으로 모든 방향 조합을 체크
✅ 결론
그리디는 부분 최적에만 집중하기 때문에 전체 최적을 보장하지 못합니다.
이 문제처럼 전체 조합의 결과에 따라 결과가 달라지는 문제는
반드시 백트래킹(DFS)으로 풀어야 합니다.
Code
# GPT
import sys
import copy
# 입력 받기
N, M = map(int, sys.stdin.readline().split())
office = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
# 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)], [(-1, 0), (0, -1)], [(1, 0), (0, -1)], [(1, 0), (0, 1)]], # ㅗ, ┌, ┘, └
4: [[(-1, 0), (0, 1), (0, -1)], [(-1, 0), (1, 0), (0, -1)], [(1, 0), (0, 1), (0, -1)], [(1, 0), (-1, 0), (0, 1)]], # ┴, ┤, ┬, ├
5: [[(-1, 0), (1, 0), (0, 1), (0, -1)]] # 모든 방향
}
# CCTV 위치 저장
cctvs = []
for i in range(N):
for j in range(M):
if 1 <= office[i][j] <= 5:
cctvs.append((i, j, office[i][j])) # (x, y, type)
# 특정 방향으로 감시 수행
def monitor(board, x, y, directions):
for dx, dy in directions:
nx, ny = x, y
while True:
nx += dx
ny += dy
if 0 <= nx < N and 0 <= ny < M:
if board[nx][ny] == 6: # 벽을 만나면 중단
break
if board[nx][ny] == 0: # 감시할 수 있는 공간
board[nx][ny] = '#'
else:
break # 범위를 벗어나면 중단
# DFS를 활용한 완전 탐색
min_blind_spots = float('inf')
def dfs(depth, board):
global min_blind_spots
if depth == len(cctvs):
# 사각지대 개수 카운트
count = sum(row.count(0) for row in board)
min_blind_spots = min(min_blind_spots, count)
return
x, y, cctv_type = cctvs[depth]
# CCTV의 모든 가능한 방향 탐색
for directions in cctv_directions[cctv_type]:
new_board = copy.deepcopy(board)
monitor(new_board, x, y, directions)
dfs(depth + 1, new_board) # 다음 CCTV 탐색
# DFS 시작
dfs(0, office)
# 최소 사각지대 출력
print(min_blind_spots)
'Algorithm > BOJ' 카테고리의 다른 글
| [BOJ] 6087번: 레이저 통신 (0) | 2025.03.21 |
|---|---|
| [BOJ] 2110번: 공유기 설치 (Aggressive cows) (이분탐색, BST) (0) | 2025.03.21 |
| [BOJ] 1253번: 좋다 (0) | 2025.03.21 |
| [BOJ] 3273번: 두 수의 합 (two-pointer) / sliding window, hash set (0) | 2025.03.20 |
| [BOJ] 2138번: 전구와 스위치 (Greedy) (0) | 2025.03.20 |