문제
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.
연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.
일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.
예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.
2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.
2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
바이러스가 퍼진 뒤의 모습은 아래와 같아진다.
2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.
연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.
빈 칸의 개수는 3개 이상이다.
출력
첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.
예제 입력 1
7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
문제풀이 생각
1) 바이러스는 '2' 이며 상하좌우의 인접한 빈칸(0)으로만 이동이 가능하기 때문에
먼저 '2'인 칸들을 모두 큐에 넣어준 후에,
BFS(너비우선탐색)을 통해 큐에서 하나씩 꺼내 확장시키는 방식
(2인 칸에서 시작하여 주변의 0인 칸들을 2로 만드는 방식)
2) 이 때, 어디에 벽을 세워야 최댓값이 나올지는 알 수 없기 때문에 벽을 세울 수 있는 모든 경우의 수에 대해 수행 필요
따라서, (1, 1) 칸 부터 (n, m)칸 까지 중 빈칸을 순서대로 하나씩 3개 선택하여
벽을 세우고 BFS를 수행한 후 벽을 지우고
그 다음칸에 대해 다시 벽을 세우고 BFS를 수행하고 벽을 지우는 방식을 반복해야 한다.
즉, 백트래킹 방식을 이용해 3개의 벽을 모든 칸에 세워본다.
3) 이렇게 진행하면서 최댓값을 저장한 후, 모든 탐색이 끝난 후 최댓값을 출력
from collections import deque
import copy
def bfs():
queue = deque()
tmp_graph = copy.deepcopy(graph)
for i in range(n):
for j in range(m):
if tmp_graph[i][j] == 2:
queue.append((i, j))
while queue:
x, y = queue.popleft()
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 tmp_graph[nx][ny] == 0:
tmp_graph[nx][ny] = 2
queue.append((nx, ny))
global answer
cnt = 0
for i in range(n):
cnt += tmp_graph[i].count(0)
answer = max(answer, cnt)
def makeWall(cnt):
if cnt == 3:
bfs()
return
for i in range(n):
for j in range(m):
if graph[i][j] == 0:
graph[i][j] = 1
makeWall(cnt+1)
graph[i][j] = 0
n, m = map(int, input().split())
graph = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
for i in range(n):
graph.append(list(map(int, input().split())))
answer = 0
makeWall(0)
print(answer)Python
문제이해
1) 바이러스(BFS, DFS), 끝까지 탐구(DFS)
2) 연구소에 벽을 세움(바이러스 퍼지는 것 방지)
3) 바이러스와 관련된 문제 생각해보기(미로탈출)
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())))
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 nx >= 0 and nx < n and ny >= 0 and ny < m:
if temp[nx][ny] == 0: #0은 빈칸, 1은 벽, 2는 바이러스
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(count):
global result
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)JAVA
import java.util.*;
public class Main {
public static int n, m, result = 0;
public static int[][] arr = new int[8][8]; // 초기 맵 배열
public static int[][] temp = new int[8][8]; // 벽을 설치한 뒤의 맵 배열
// 4가지 이동 방향에 대한 배열
public static int[] dx = {-1, 0, 1, 0};
public static int[] dy = {0, 1, 0, -1};
// 깊이 우선 탐색(DFS)을 이용해 각 바이러스가 사방으로 퍼지도록 하기
public static void virus(int x, int y) {
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 상, 하, 좌, 우 중에서 바이러스가 퍼질 수 있는 경우
if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
if (temp[nx][ny] == 0) {
// 해당 위치에 바이러스 배치하고, 다시 재귀적으로 수행
temp[nx][ny] = 2;
virus(nx, ny);
}
}
}
}
// 현재 맵에서 안전 영역의 크기 계산하는 메서드
public static int getScore() {
int score = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (temp[i][j] == 0) {
score += 1;
}
}
}
return score;
}
// 깊이 우선 탐색(DFS)을 이용해 울타리를 설치하면서, 매 번 안전 영역의 크기 계산
public static void dfs(int count) {
// 울타리가 3개 설치된 경우
if (count == 3) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
temp[i][j] = arr[i][j];
}
}
// 각 바이러스의 위치에서 전파 진행
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (temp[i][j] == 2) {
virus(i, j);
}
}
}
// 안전 영역의 최대값 계산
result = Math.max(result, getScore());
return;
}
// 빈 공간에 울타리를 설치
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 0) {
arr[i][j] = 1;
count += 1;
dfs(count);
arr[i][j] = 0;
count -= 1;
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
arr[i][j] = sc.nextInt();
}
}
dfs(0);
System.out.println(result);
}
}