1. 시간 복잡도 체크
입력 조건
- N, M ≤ 8 → 최대 64칸
- 바이러스 ≤ 10
- 빈칸 ≥ 3
시간 복잡도 판단
전체 탐색 공간이 매우 작기 때문에, 연산량을 사실상 상수 수준(O(1))으로 취급할 수 있음
=> 완전 탐색, 백트래킹(완탐 하위 개념), BFS, DFS 모두 사용 가능
2. 알고리즘 결정 과정
1) 문제의 구조 판단 — 전형적인 BFS/DFS 확산 문제
- 바이러스가 여러 지점에서 동시에 시작하고
- 상하좌우로 퍼지며
- 더 이상 확산할 곳이 없을 때 종료됨→ 이는 “그래프에서 영역을 확장하는 구조”로, 전형적인 BFS/DFS 패턴
BFS 한 번의 비용: O(64) → 사실상 상수
2) 벽 3개의 최적 위치는 규칙으로 찾을 수 없음 → 완전 탐색 필요
벽 3개 위치 조합의 특징:
- 부분적으로 좋은 선택이 전체 해에 기여한다는 보장이 없음
- DP 불가능 (최적 부분 구조 성립 X)
- 그리디 불가능 (지역 최적이 전체 최적이 아님)
- 이분탐색 불가능 (단조성 없음)
- 수학적 규칙 없음 (반례 다수)
즉, 정답 위치를 추론할 방법 자체가 없음
따라서:
가능한 모든 벽 3개 조합을 탐색(완전 탐색)
각 조합마다 BFS로 확산을 시뮬레이션
→ 결과 비교하여 최대 안전 영역 도출
3) 최종 코드
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
# 빈 칸, 바이러스 위치 미리 저장해두기
empties = []
virus = []
for y in range(n):
for x in range(m):
if graph[y][x] == 0:
empties.append((x, y))
elif graph[y][x] == 2:
virus.append((x, y))
L = len(empties)
answer = 0
def bfs():
# deepcopy 금지 → 리스트 슬라이싱 사용
temp = [row[:] for row in graph]
q = deque(virus)
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < m and 0 <= ny < n:
if temp[ny][nx] == 0:
temp[ny][nx] = 2
q.append((nx, ny))
# 안전 영역 세기
safe = 0
for y in range(n):
for x in range(m):
if temp[y][x] == 0:
safe += 1
return safe
def build_wall(start, count):
global answer
if count == 3:
answer = max(answer, bfs())
return
# 조합 중복 제거: start index부터만 탐색
for i in range(start, L):
x, y = empties[i]
if graph[y][x] == 0:
graph[y][x] = 1
build_wall(i + 1, count + 1)
graph[y][x] = 0
build_wall(0, 0)
print(answer)4) 주의할 점
- map 복사 시 deepcopy 쓰면 시간 초과
- 벽 조합 중복 허용하면 시간 초과
- 바이러스 위치 매번 탐색하면 시간 초과
-> 빈 칸 3개를 골라 벽을 세우고 -> BFS -> 안전 영역 계산 -> 되돌려서 이거 반복
벽 조합용
def backtrack(start, count):
if count == 3: # 벽 3개 완료
simulate()
return
for i in range(start, len(empties)): # 중복 제거(중요)
x, y = empties[i]
graph[y][x] = 1 # 선택
backtrack(i + 1, count + 1)
graph[y][x] = 0 # 취소
다중 시작점 BFS
- 바이러스가 여러 곳에 있으므로 큐에 모든 바이러스 좌표를 넣고 시작
BFS 핵심 흐름
- map을 복사
- 큐에 virus 좌표 모두 넣기
- BFS로 퍼뜨리기
- 남은 0의 개수 세기 → 안전 영역
3. 해당 알고리즘 관련 하위 문제
백트래킹
BOJ 15649 N과 M (1): https://www.acmicpc.net/problem/15649
백트래킹이란?
완전 탐색을 '가능한 한 덜 비효율적으로' 수행하는 기법
- 완전 탐색 = 모든 경우를 끝까지 다 본다
- 백트래킹 = 가능성 없는 건 중단
=> 옵션 너무 많은 문제도 처리 가능
백트래킹 문제를 푸는 틀
백트래킹 3단 구성
1. 선택: 현재 수열/상태에 어떤 값을 넣음
2. 재귀: 그 상태에서 다음 선택을 하러 깊이 들어감
3. 취소: 이전 선택을 되돌림(pop, visited=False 등)
=> 이 3개가 반복되며 가능한 모든 경우의 수를 탐색하는 구조
def backtrack(depth):
# 1) 종료 조건: 원하는 깊이까지 도달하면 정답 처리
if depth == 목표_길이:
정답 처리
return
# 2) 현재 depth에서 선택할 수 있는 모든 '후보'를 순회
# → 여기서 가능한_리스트는 문제에 따라 달라짐
for 후보 in 가능한_리스트:
# 3) 이 후보를 지금 depth에서 사용할 수 있는지 검사
# 중복 사용 금지 / 방문 여부 체크 / 조건 체크 등
if 사용 가능(= visited 체크 or 조건 만족):
# 4) 후보 선택 (상태 갱신)
상태 갱신(선택)
# 5) 더 깊은 단계로 이동해 다음 선택을 시도
backtrack(depth + 1)
# 6) 돌아오면서 상태 복구 (백트래킹)
상태 복원(취소)
풀이 코드
n, m = map(int, input().split())
visited = [False] * (n+1) #방문 체크
selected = []
def backtrak():
# 1) 종료 조건: 수열 중 m개를 다 골랐으면 (길이가 m인 수열)
if len(selected) == m:
print(*selected) #*selected가 뭐임 => 리스트 풀어서 개별인자로 출력
return
# 2) 1~n 숫자 중 아직 안 쓴 숫자 선택
for num in range(1, n+1):
if not visited[num]:
visited[num] = True #True는 다시 가지 않아 중복 X
selected.append(num)
backtrak() #재귀로 다음 자리 탐색
selected.pop() #백트래킹(도로 빼기)
visited[num] = False #방문 해제
backtrak()BFS/DFS
여러 시작점 BFS
BOJ 1012 유기농 배추: https://www.acmicpc.net/problem/1012
1. 문제 분석
내 판단
- 인접한 영역(이어진 덩어리)의 개수를 세는 문제 → BFS/DFS 유형
- 입력으로 주어지는 건 “배추 좌표 목록”뿐이므로, 좌표를 이용해서 직접 배추밭 2차원 배열(map) 을 만들어야 함
- 상/하/좌/우로 인접한 칸을 확인해야 하므로 방향 리스트(dx, dy) 필요
- 배추가 있는 칸(=1)에서 BFS/DFS를 한 번 돌면 그 배추와 연결된 영역 전체를 한 번에 방문
→ 연결된 영역 하나당 지렁이 1마리 필요 → 영역 개수 = 지렁이 수
2. 최종 코드
from collections import deque
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
def bfs(x, y): # (x,y): (가로,세로)
que = deque()
que.append((x, y))
visited[y][x] = True # (y,x)
while que:
x, y = que.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 범위 체크 (x는 가로, y는 세로)
if 0 <= nx < m and 0 <= ny < n:
if not visited[ny][nx] and map_lst[ny][nx] == 1:
visited[ny][nx] = True
que.append((nx, ny))
t = int(input())
for _ in range(t):
m, n, k = map(int, input().split()) # m=가로, n=세로
# map[y][x] 형태로 생성
map_lst = [[0]*m for _ in range(n)]
visited = [[False]*m for _ in range(n)]
for _ in range(k):
x, y = map(int, input().split()) # (x:가로, y:세로)
map_lst[y][x] = 1
cnt = 0
for y in range(n): # 세로 먼저
for x in range(m): # 가로
if map_lst[y][x] == 1 and not visited[y][x]:
bfs(x, y)
cnt += 1
print(cnt)
3. 구현하면서 헷갈렸던 부분 정리
좌표(x, y)와 배열 인덱스[row][col]을 섞어서 쓴 것
- 문제에서 주는 좌표:
-x: 가로(m) -> 열(col)y: 세로(n) -> 행(row)
- 파이썬 2차원 리스트:
-arr[row][col]=arr[y][x] - 좌표계 입력
(x=2, y=1)- 2차원 배열 구조: 1행 2열이라고 보통 말하잖아 그런 거지...
행(y) 0: [ ][ ][ ][ ][ ]
행(y) 1: [ ][ ][ X ][ ][ ]
행(y) 2: [ ][ ][ ][ ][ ]
0 1 2 3 4 ← x4. BFS란?
"가까운 칸부터 차례대로 퍼져나가는 탐색"
판단 체크 리스트
BFS
- 가까운 곳부터 차례대로 -> 층(layer) 단위 참색
- 보통 큐 사용
- 최단 거리, 최소 횟수, 레벨별 탐색 유리
DFS - 한쪽으로 끝까지 쭉 파고 들어갔다가 다시 돌아오는 방식
- 재귀 or 스택 사용
- 경로 찾기, 백트래킹, 완전 탐색에 자주 사용
다음 질문 중에 “예”가 여러 개 나오면 BFS/DFS를 의심
1. 그래프나 격자(2차원 배열)가 등장하는가?
- 예: 지도, 미로, 배추밭, 섬, 빙산, 토마토 상자, 방
2. 인접한 것끼리 연결되어 있다는 표현이 나오는가?
- 예: 상하좌우로 인접, 8방향 인접, 간선으로 연결, 친구 관계, 컴퓨터 네트워크
3. “몇 칸 만에, 최소 몇 번 만에” 같은 최단 거리 느낌이 있는가?
- 예: 최소 이동 횟수, 최소 시간, 제일 빨리 도착하는 경우
→ 이 경우는 BFS가 1순위 후보
4. “덩어리/영역의 개수”를 세는 문제인가?
- 예: 섬의 개수, 영역의 개수, 연결된 그룹 개수
→ BFS/DFS 둘 다 가능
5. 탐색 도중에 다시 돌아가면서 모든 경우를 시도해야 하는가?
- 예: 모든 순열/조합, 모든 경로, 조건을 만족하는 모든 경우 찾기
→ 이건 BFS라기보다 DFS + 백트래킹
유기농 배추(1012)는
“인접한 영역의 개수” + “상하좌우로 연결” → BFS/DFS 둘 다 가능하지만,
나는 큐에 익숙해지는 목적 + 전형적인 예제라서 BFS로 풂
5. BFS 푸는 틀
핵심 구조
- visited 체크
- 그래프(이웃 정보) 반복
- 조건 만족 시 탐색 확장
- BFS는 큐, DFS는 재귀/스택
1차원 DFS/BFS 기본 틀 (그래프 기반)
DFS(재귀)
def dfs(node):
visited[node] = True
for nxt in graph[node]:
if not visited[nxt]:
dfs(nxt)
BFS(큐)
from collections import deque
def bfs(start):
q = deque([start])
visited[start] = True
while q:
cur = q.popleft()
for nxt in graph[cur]:
if not visited[nxt]:
visited[nxt] = True
q.append(nxt)2차원 DFS/BFS 기본 틀 (격자 탐색)
격자 탐색: "주변 칸을 그래프의 이웃으로 간주"한 BFS/DFS 확장판
필요 요소 추가
- 방향 리스트(dx, dy)
- 범위 체크(0<=nx<m, 0<=ny<n)
- map[y][x] 접근
DFS(재귀)
def dfs(x, y):
visited[y][x] = True
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < m and 0 <= ny < n:
if not visited[ny][nx] and grid[ny][nx] == 1:
dfs(nx, ny)
BFS(큐)
from collections import deque
def bfs(x, y):
q = deque([(x, y)])
visited[y][x] = True
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < m and 0 <= ny < n:
if not visited[ny][nx] and grid[ny][nx] == 1:
visited[ny][nx] = True
q.append((nx, ny))
2차원 배열 + 영역 크기 BFS (문제 구조 유사)
BOJ 2583 영역 구하기: https://www.acmicpc.net/problem/2583
1. 문제 분석
내 판단
- n, m이 자연수이고 최대가 100 정도라서 BFS/DFS, 완전 탐색, 백트래킹 정도 가능하다고 생각
- 문제의 목표가 "분리된 영역의 개수와 넓이"를 구하는 것 => BFS/DFS로 영역을 묶는 방식이 적합하다고 판단
- 먼저 전체 맵을 만든 뒤, 입력으로 주어진 직사각형이 위치한 부분을 막고, 직사각형이 없는 나머지 공간을 BFS로 탐색해 연결된 칸들을 하나의 영역으로 볼 수 있다고 생각
- BFS 한 사이클 = 영역 1개
2. 최종 코드
from collections import deque
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
def bfs(x, y):
que = deque()
que.append((x, y))
visited[y][x] = True
area = 1
while que:
x, y = que.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < m and 0 <= ny < n:
if not visited[ny][nx] and map_lst[ny][nx] ==1:
visited[ny][nx] = True
area += 1
que.append((nx, ny))
return area
n, m, k = map(int, input().split())
areas = []
map_lst = [[1]*m for _ in range(n)]
visited = [[False]*m for _ in range(n)]
for _ in range(k):
x1, y1, x2, y2 = map(int, input().split())
for i in range(y1, y2):
for j in range(x1, x2):
map_lst[i][j] = 0
cnt = 0
for y in range(n):
for x in range(m):
if map_lst[y][x] and not visited[y][x]:
area_size = bfs(x, y)
areas.append(area_size)
areas.sort()
print(len(areas))
print(*areas)
3. 구현하면서 헷갈렸던 부분들 정리
areas 리스트 개념이 처음에 헷갈림
- BFS 한 번 돌 때마다 얻는 넓이를 하나씩 append해야 함
- 최종 출력은
print(*areas)형태로, 리스트를 "공백으로 나열해서 출력"해야 문제 출력 현상과 동일해짐
areas = [3, 5, 2]
print(*areas) # 3 5 2
print(areas) [3, 5, 2]
기술 블로그