백준 14502번 - 연구소

연구소 문제 바로 가기

풀이 날짜: 2026-01-07

baekjoon 알고리즘 문제 풀이

풀이 코드


import sys
input = sys.stdin.readline

dx = [0,0,-1,1]
dy = [-1,1,0,0]

n,m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
temp = [[0]*m for _ in range(n)]

result = 0

empty = []
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            empty.append((i,j))

def virus(x,y):
    for i in range(4):
        nx = dx[i] + x
        ny = dy[i] + y
        if 0<=nx<n and 0<=ny<m and temp[nx][ny] == 0:
            temp[nx][ny] = 2
            virus(nx,ny)

def get_score():
    score = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                score += 1
    return score

def dfs(start, count):
    global result
    if count == 3:
        for i in range(n):
            for j in range(m):
                temp[i][j] = graph[i][j]

        for i in range(n):
            for j in range(m):
                if temp[i][j] == 2:
                    virus(i,j)

        result = max(result, get_score())
        return

    for i in range(start, len(empty)):
        x,y = empty[i]
        if graph[x][y] == 0:
            graph[x][y] = 1
            dfs(i+1, count+1)
            graph[x][y] = 0
dfs(0,0)
print(result)

문제 핵심 요약:

빈칸 3개를 골라 벽을 세운 뒤, 바이러스를 퍼뜨렸을 때
남아있는 안전영역(0의 개수)이 최대가 되는 값을 구하는 문제이다.

즉, ‘최적의 3칸 선택’이 핵심이다.
결국 빈칸 중 3개를 조합으로 고르고(완전탐색) 바이러스 확산 시뮬레이션을 돌린 후 안전영역 계산을 반복하면 된다.

내가 선택한 풀이 방식

1) 벽 3개 세울 위치를 ‘조합’으로 뽑기 빈칸(0) 리스트를 empty에 미리 모아뒀다.
이 빈칸들 중 서로 다른 3개를 골라야 하니까

DFS에서 start 인덱스를 두고
for i in range(start, len(empty)) 방식으로 탐색하면
같은 조합을 중복해서 뽑지 않게 된다.
dfs(i+1, count+1)로 다음 선택은 항상 더 뒤에서만 하게 만들어서 중복을 방지한다.

2) 벽을 세운 상태를 temp에 복사하기 벽 3개를 다 세웠다면(count == 3)

temp에 현재 graph 상태를 그대로 복사한다.
이후 바이러스 확산은 temp에서만 수행한다. 왜냐하면,
원본 graph는 다음 조합 탐색을 위해 항상 깨끗해야 한다.
따라서 매 조합마다 temp를 새로 만든 뒤, 그 복사본에서만 퍼뜨리는 방식이 안전하다.

3) 바이러스 확산 temp[i][j]==2인 모든 위치에서 바이러스 확산을 시작한다.

상하좌우로 이동하면서 0이면 2로 바꾸고
그 위치에서 다시 퍼뜨린다(재귀)
즉, 연결된 0 영역을 전부 감염시킨다.

4) 최댓값 갱신 바이러스 확산이 끝난 temp에서 0의 개수를 세면 ‘안전영역’이 된다.

result = max(result, get_score())

백트래킹의 본질

왜 graph[x][y] = 0 으로 반드시 되돌려야 할까?

이 문제에서 가장 헷갈렸던 부분은, 왜 벽을 세운 뒤에 다시 0으로 되돌려야 하는가였다.

DFS는 ‘여러 개의 지도’를 쓰는 게 아니라 ‘하나의 지도’를 돌려 쓴다.

이 문제에서 graph는 매 경우마다 새로 만들어지는 것이 아니라, 하나의 graph를 계속 수정하면서 여러 경우를 시도하는 것이다.
즉, DFS는

같은 지도 위에 벽을 세웠다가
그 실험이 끝나면 다시 원래 상태로 돌아와서
다음 선택을 시도하는 구조였다.

따라서 DFS의 내용은 다음과 같다.

graph[x][y] = 1 : “이 선택지를 한 번 선택해본다”
dfs(…) : “이 선택을 했을 때 벌어질 수 있는 모든 경우를 끝까지 본다”
graph[x][y] = 0 : “이 선택은 취소하고, 다음 선택을 공정하게 보기 위해 원상복구한다”