16_연구소

14502번: 연구소

안전 구역의 크기의 최댓값을 구하는 문제다.

벽은 3개 설치할 수 있는데, 벽은 안전구역에 설치할 수 있다.

전체 그래프 크기 N*M = 8*8 <= 64이므로 생각보다 작았다.

그리고 시간 제한이 2초였다.

아런 것들을 딱 보고, 이거 그냥 벽 3개 고를 수 있는 모든 경우의 수마다 DFS 돌면서 탐색한 다음에, 안전구역 개수 세서 최댓값 구하면 되는거 아닌가? 라는 생각이 들었다.

그리고 이 생각이 딱 맞았다.

 

---

내 풀이 코드

# 14502번: 연구소
from itertools import combinations
import copy, sys

sys.setrecursionlimit(10**6)

n, m = map(int, input().split()) # 가로, 세로 길이
virus = [] # 바이러스의 좌표를 저장하고 있는 리스트
empty = [] # 빈 칸의 좌표를 저장하고 있는 리스트(벽을 세울 수 있는 후보들을 저장하고 있는 리스트)
graph = []
for r in range(n):
    row = list(map(int, input().split()))
    graph.append(row)
    for c in range(m):
        if graph[r][c] == 2:
            virus.append((r, c))
        elif graph[r][c] == 0:
            empty.append((r, c))


dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited = [[False] * m for _ in range(n)] # 방문여부를 저장하는 리스트

def dfs(x, y, graph, visited):
    visited[x][y] = True
    graph[x][y] = 300 # 바이러스가 퍼져버린 칸은 300임


    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        # 칸을 초과하는 경우
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
        # 벽으로 간 경우
        if graph[nx][ny] == 1:
            continue
        # 다른 바이러스의 칸으로 간 경우
        # if graph[nx][ny] == 2:
        #     continue
        if not visited[nx][ny]:
            if graph[nx][ny] == 0 or graph[nx][ny] == 2:
                dfs(nx, ny, graph, visited)


# 안전 영역의 개수를 리턴해주는 함수
def check_safe_place(graph):
    n = len(graph)
    m = len(graph[0])
    answer = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                answer += 1

    return answer




wall_candidate = list(combinations(empty, 3)) # 벽을 설치할 수 있는 좌표 3개씩을 저장한 리스트

temp_graph = copy.deepcopy(graph)
temp_visited = copy.deepcopy(visited)

answer = 0

for candidate in wall_candidate:
    for w_x, w_y in candidate:
        temp_graph[w_x][w_y] = 1
    for v in virus:
        x, y = v
        dfs(x, y, temp_graph, temp_visited)
    answer = max(answer, check_safe_place(temp_graph))
    temp_graph = copy.deepcopy(graph)
    temp_visited = copy.deepcopy(visited)


print(answer)

나는 DFS를 통해 풀었다.

그리고 벽이 될 수 있는 경우의 수를 itertools 라이브러리의 combination를 사용해서 풀었다.

다른 풀이를 보니 combination을 사용하지 않고, DFS/BFS를 통해 벽이 될 수 있는 경우의 수를 구할 수도 있다고 한다.

즉, 안전 영역을 계산할 때 외에도 벽이 될 수 있는 경우의 수를 구할 때도 DFS/BFS를 또 쓰는 것이다.

 

 

 

다른 풀이 코드

# 14502번: 연구소
n, m = map(int, input().split())

data = [] # 초기 맵 리스트
temp = [[0] * m for _ in range(n)] # 벽을 설치한 뒤의 맵 리스트

for _ in range(n):
    data.append(list(map(int, input().split())))


# 4가지 이동 방향에 대한 리스트
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

result = 0

# DFS를 이용해 각 바이러스가 사방으로 퍼지도록 하기
def virus(x, y):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 상, 하, 좌, 우 중 바이러스가 퍼질 수 있는 경우
        if nx >= 0 and nx < n and ny >= 0 and ny < m:
            if 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

# DFS를 이용해 울타리를 설치하면서, 매번 안전 영역의 크기 계산
def dfs(count):
    global result
    # 울타리가 3개 설치된 경우
    if count == 3:
        for i in range(n):
            for j in range(m):
                temp[i][j] = data[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 data[i][j] == 0:
                data[i][j] = 1
                count += 1
                dfs(count)
                data[i][j] = 0
                count -= 1

dfs(0)
print(result)

 

위 방식은 백트래킹을 활용하는 방법이기도 하다.

아래 링크를 참고해서 이 문제에 사용된 백트래킹 기법에 대해 이해하자.

https://great-park.tistory.com/104