728x90
반응형
14502 - 연구소
https://www.acmicpc.net/problem/14502


문제
바이러스 확산을 막기 위해 연구소 벽을 세우려 함
연구소 크기 NxM 직사각형, 직사각형은 1x1 정사각형으로 나눠져 있음
/ 빈 칸, 벽으로 이뤄져 있으며 벽은 칸 하나를 가득 차지
/ 일부 칸은 바이러스 존재, 상하좌우로 인접한 빈 칸 모두 퍼져나갈 수 있음
/ 세울 수 있는 벽의 개수 3개고 꼭 세워야 함
=> 연구소 지도가 주어졌을 때 얻을 수 있는 안전 영역의 크기의 최댓값
입력
첫째 줄: 지도의 세로 크기 N, 가로 크기 M (3 <= N, M <= 8)
둘째 줄 ~ N개의 줄: 지도 모양 (0 빈 칸, 1 벽, 2 바이러스)
(2 <= 2의 개수 <= 10, 3 <= 빈 칸 개수)
출력: 얻을 수 있는 안전 영역의 최대 크기
풀이
DFS(백트래킹)
벽 세우기
- 벽 3개 세우면 바이러스 퍼트리기(`bfs()`)
- 지도 순회하면서 빈 칸(0) => 벽 3개 세운 모든 조합 시도
- `map[i][j] = 1`: 벽 세우기
- `dfs(cnt + 1)`: 벽 하나 더 생겼으니 다음 벽 세우러 재귀 호출
- `map[i][j] = 0`: 재귀 끝나면 벽 다시 지움 (원상 복구)
static void dfs(int cnt) {
if (cnt == 3) {
bfs();
return;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 0) {
map[i][j] = 1;
dfs(cnt + 1);
map[i][j] = 0;
}
}
}
}
BFS
바이러스 퍼트리고 남은 빈 칸 계산해서 `maxSafe` 갱신
- `copy`: `map`은 DFS에서 벽 세우며 변함 -> 별도의 `copy`에서 시뮬레이션 => 원본 보존
- 초기 바이러스(2) 큐에 넣고 하나씩 꺼내면서 상하좌우 확산
static void bfs() {
int[][] copy = new int[N][M];
Queue<int[]> q = new LinkedList<>();
// 지도 복사 + 바이러스 위치 저장
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
copy[i][j] = map[i][j];
if (copy[i][j] == 2) q.offer(new int[]{i, j});
}
}
// 바이러스 퍼뜨리기
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int d = 0; d < 4; d++) {
int nx = cur[0] + dx[d];
int ny = cur[1] + dy[d];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if (copy[nx][ny] == 0) {
copy[nx][ny] = 2;
q.offer(new int[]{nx, ny});
}
}
}
// 안전 구역 계산
int safe = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (copy[i][j] == 0) safe++;
}
}
maxSafe = Math.max(maxSafe, safe);
}
코드
import java.io.*;
import java.util.*;
// 연구소
public class boj_14502 {
static int N, M;
static int[][] map;
static int maxSafe = 0;
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static void dfs(int cnt) {
if (cnt == 3) {
bfs();
return;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 0) {
map[i][j] = 1;
dfs(cnt + 1);
map[i][j] = 0;
}
}
}
}
static void bfs() {
int[][] copy = new int[N][M];
Queue<int[]> q = new LinkedList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
copy[i][j] = map[i][j];
if (copy[i][j] == 2) q.offer(new int[]{i, j});
}
}
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int d = 0; d < 4; d++) {
int nx = cur[0] + dx[d];
int ny = cur[1] + dy[d];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if (copy[nx][ny] == 0) {
copy[nx][ny] = 2;
q.offer(new int[]{nx, ny});
}
}
}
int safe = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (copy[i][j] == 0) safe++;
}
}
maxSafe = Math.max(maxSafe, safe);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(0);
System.out.println(maxSafe);
}
}728x90
반응형
'✏️ > BOJ' 카테고리의 다른 글
| [BOJ/DP] 백준 1106 - 호텔 (Java) (0) | 2025.11.13 |
|---|---|
| [BOJ/BFS] 백준 1707 - 이분 그래프 (Java) (0) | 2025.11.12 |
| [BOJ/Dijkstra] 백준 1504 - 특정한 최단 경로 (Java) (0) | 2025.11.11 |
| [BOJ/MST] 백준 1647 - 도시 분할 계획 (Java) (0) | 2025.11.11 |
| [BOJ] 백준 2252 - 줄 세우기 (Java) (0) | 2025.11.11 |