백준 14502번 연구소 풀러가기

1️⃣ 문제 설명

문제를 그림으로 간단히 설명하면 아래와 같다.

• Before처럼 2차원 배열이 입력으로 주어진다.
  • 0은 빈칸, 1은 벽, 2는 바이러스이다.
• 우리는 After처럼 벽(1)을 3개 세울 수 있다. (더도 말고, 덜도 말고 딱 3개)
• 바이러스는 상하좌우로 퍼져나갈 수 있다. (벽이 있으면 막혀서 퍼지지 못함)
• 이 때 바이러스가 퍼질 수 없는 칸(=0인 칸)의 최댓값을 구하자.

2️⃣ 구현 아이디어

1. 벽을 3개 세운다.
2. DFS / BFS를 사용하여 바이러스를 퍼뜨린다.
3. 바이러스가 퍼지지 않은 칸을 센다.

2번과 3번은 간단하게 구현할 수 있지만, 1번) 벽 3개의 위치 고르기 에서 벽 3개를 어떻게 골라야 할지 떠오르지 않아 다른 사람의 코드를 참고하였다.
처음에 '완전 탐색으로 그냥 해볼까?' 생각했지만, 경우의 수가 약 4만 개가 나오고 4만 개 모두를 DFS/BFS를 하면 안될 것 같았다. 🫠

벽 3개의 위치를 고르는 방법은 바로 ✨백트래킹✨이었다.

3️⃣ 코드 작성 - 시간 초과

🦠 입력

import sys

n, m = map(int, input().split()) # 세로, 가로
board = [[0 for _ in range(m)] for _ in range(n)]

for i in range(n):
    board[i] = list(map(int, input().split()))

🦠 DFS

• 스택을 사용하여 구현
• 원본 배열 보존을 위해 깊은 복사를 사용 → copy.deepcopy(board)
  • 얕은 복사 - 원본 객체의 주소값을 복사
  • 깊은 복사 - 참조된 객체 자체를 복사

import copy
from collections import deque

def dfs():
    stack = []
    visited = []
    temp = copy.deepcopy(board) # 깊은 복사
    for i in range(n):
        for j in range(m):
        	# 바이러스 시작점을 stack과 visited 배열에 담음
            if temp[i][j] == 2 and (i, j) not in visited:
                stack.append((i, j))
                visited.append((i, j))
                
    while stack:
    	# 1. 스택에서 원소를 pop한다.
        cur = stack.pop()
        dx = [-1, 0, 1, 0]
        dy = [0, -1, 0, 1]

		# 2. 인접 노드를 탐색
        for i in range(4):
            nx, ny = cur[0] + dx[i], cur[1] + dy[i]

			# 3. 보드를 벗어난 경우, 이미 방문한 경우, 빈 칸(0)이 아닌 경우 continue
            if nx<0 or nx>=n or ny<0 or ny>=m or (nx, ny) in visited or temp[nx][ny] != 0:
                continue
            # 4. 바이러스 전이
            temp[nx][ny] = 2
            # 5. 인접 노드를 스택에 넣고, 방문 처리
            stack.append((nx, ny))
            visited.append((nx, ny))

	# 바이러스가 전이되지 않은 칸을 count
    count = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                count += 1
                
    global result
    result = max(count, result)

🦠 백트래킹

def make_wall(count):
	# 벽을 3개 설치했으면, bfs를 돌며 안전 영역의 크기를 계산
    if count == 3:
        bfs()
        return

    for i in range(n):
        for j in range(m):
            if board[i][j] == 0:
                board[i][j] = 1
                make_wall(count+1)
                board[i][j] = 0

🦠 결과 출력

result = 0
make_wall(0)
print(result)

🦠 전체 코드

import sys
import copy

input = sys.stdin.readline

n, m = map(int, input().split()) # 세로, 가로
board = [[0 for _ in range(m)] for _ in range(n)]

for i in range(n):
    board[i] = list(map(int, input().split()))

def dfs():
    stack = []
    visited = []
    temp = copy.deepcopy(board)
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 2 and (i, j) not in visited:
                stack.append((i, j))
                visited.append((i, j))
                
    while stack:
        cur = stack.pop()
        dx = [-1, 0, 1, 0]
        dy = [0, -1, 0, 1]

        for i in range(4):
            nx, ny = cur[0] + dx[i], cur[1] + dy[i]

            if nx<0 or nx>=n or ny<0 or ny>=m or (nx, ny) in visited or temp[nx][ny] != 0:
                continue
            temp[nx][ny] = 2
            stack.append((nx, ny))
            visited.append((nx, ny))

    count = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                count += 1

    global result
    result = max(count, result)


def make_wall(count):
    if count == 3:
        dfs()
        return

    for i in range(n):
        for j in range(m):
            if board[i][j] == 0:
                board[i][j] = 1
                make_wall(count+1)
                board[i][j] = 0

result = 0
make_wall(0)
print(result)

4️⃣ DFS 코드 수정 - 맞았습니다

• visited 배열을 사용하지 않음
  • 칸을 세는 문제가 아니기 때문에 이미 방문한 경우 2로 만들지 않는다!라는 조건이 필요가 없다.
  • 그러므로 visited 배열을 사용하지 않는 것을 통해 연산 횟수를 줄일 수 있다.

def dfs():
    stack = []
    temp = copy.deepcopy(board)
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 2:
                stack.append((i, j))
                
    while stack:
        cur = stack.pop()
        dx = [-1, 0, 1, 0]
        dy = [0, -1, 0, 1]

        for i in range(4):
            nx, ny = cur[0] + dx[i], cur[1] + dy[i]

            if nx<0 or nx>=n or ny<0 or ny>=m or temp[nx][ny] != 0:
                continue
            temp[nx][ny] = 2
            stack.append((nx, ny))

    count = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                count += 1

    global result
    result = max(count, result)