[백준] 연구소

subin·2023년 4월 14일

🥰Coding Test

목록 보기

16/22

문제

https://www.acmicpc.net/problem/14502

TC

DFS

인접 행렬로 구현할 시 O(V^2)
인접 리스트로 구현할 시 O(V+E)

BFS

인접 행렬로 구현할 시 O(V^2)
인접 리스트로 구현할 시 O(V+E)

Idea

역시 삼성 기출이다. 전형적인 DFS, BFS 문제이고, 가로 세로 최대 길이가 8이라서 시간복잡도에 제한이 없어 문제 그대로 구현만 하면 된다.

그래프 탐색을 하면서 3곳에 벽을 세우고 바이러스를 확산시킨 다음에 안전 영역을 최대로 갱신 시켜주면 된다.

입력 받은 기본 배열은 변경되지 않게 하기 위해 deepcopy (내 풀이에서는 그냥 for문으로 직접 값을 옮겼다) 해서 사용하면 된다.

code (Python)

DFS 풀이

n, m = map(int, input().split())
# 0=빈 칸, 1=벽, 2=바이러스
graph = [list(map(int, input().split())) for _ in range(n)]
temp_graph = [[0 for _ in range(m)] for _ in range(n)]

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

# 바이러스 확산시키는 함수
def virus(x, y):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < m:
            if temp_graph[nx][ny] == 0:
                temp_graph[nx][ny] = 2
                virus(nx, ny)

# 안전 영역의 크기 구하는 함수
def get_score():
    cnt = 0
    for x in range(n):
        for y in range(m):
            if temp_graph[x][y] == 0:
                cnt += 1

    return cnt

result = 0
def dfs(graph, cnt):
    global result

    if cnt == 3:
        # 원래 배열 변경 막기 위해 deepcopy 방식으로 배열 값 옮기기
        for i in range(n):
            for j in range(m):
                temp_graph[i][j] = graph[i][j]

        for i in range(n):
            for j in range(m):
                # 바이러스가 있는 위치라면 확산시키기
                if temp_graph[i][j] == 2:
                    virus(i, j)

        # 안전 영역의 최대 크기 갱신
        result = max(result, get_score())
        return

    for i in range(n):
        for j in range(m):
            # 빈 칸이면 벽 세워보기
            if graph[i][j] == 0:
                graph[i][j] = 1
                dfs(graph, cnt+1)
                graph[i][j] = 0

dfs(graph, 0)
print(result)

BFS 풀이

from collections import deque

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

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

# 바이러스 확산시키는 함수
def virus(x, y):
    queue = deque()
    queue.append((x, y))

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 범위 내이고, 빈 칸이라면 바이러스 확산시키기
            if 0 <= nx < n and 0 <= ny < m and temp[nx][ny] == 0:
                temp[nx][ny] = 2
                queue.append((nx, ny))

# 안전 영역의 크기 구하는 함수
def get_score():
    cnt = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                cnt += 1

    return cnt

result = 0
def make_wall(cnt):
    global result

    if cnt == 3:
        for i in range(n):
            for j in range(m):
                # deepcopy 용도
                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(n):
        for j in range(m):
            # 빈 칸이면 벽 세워보기
            if graph[i][j] == 0:
                graph[i][j] = 1
                make_wall(cnt + 1)
                graph[i][j] = 0

make_wall(0)
print(result)