1. 문제
https://www.acmicpc.net/problem/14502
2. 풀이 과정
이 문제는 N x M 크기의 맵이 주어지고, 각 영역은 빈 칸(0), 벽(1), 바이러스(2)로 구분된다.
바이러스는 벽을 통과 못한다. 벽 3개를 추가로 설치할 수 있으며, 이 때 안전 영역의 최대 개수를 구하는 문제이다.
N, M의 최대크기는 8인데 제한시간이 2초로 비교적 여유롭다.
문제 접근
1. 3개의 벽을 치는 모든 케이스를 모두 구한다.
- DFS, 백트래킹을 통해 3개의 벽을 치는 모든 케이스를 구한다.
- 각 케이스 마다 BFS를 통해 감염처리를 하고 안전영역의 개수를 구해서 최대값을 갱신한다.
static void dfs(int depth) {
if (depth == 3) {
// 3개의 벽을 모두 설치한 상태
MAX = Math.max(MAX, safeZone);
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(depth + 1);
map[i][j] = 0;
}
}
}
}
2. 각 케이스마다 BFS를 통해 감염 영역을 확장해간다.
- 여기서 중요한 것은 여러 케이스를 고려해야 하기 때문에, map(원본 배열)을 사용하지 않는다.
- 복사본을 사용하여 감염처리를 한다.
static int bfs() {
Queue<Point> q = new LinkedList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 2) {
q.offer(new Point(i, j));
}
}
}
int[][] copyMap = new int[N][M];
for (int i = 0; i < N; i++) {
copyMap[i] = map[i].clone();
}
while (!q.isEmpty()) {
Point cur = q.poll();
for (int i = 0; i < 4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if (nx < 0 || nx >= N || ny < 0 || ny >= M || copyMap[nx][ny] != 0) {
continue;
}
q.offer(new Point(nx, ny));
copyMap[nx][ny] = 2;
}
}
return getSafeZone(copyMap); // 안전 영역 개수를 구한다.
}
3. 각 케이스마다 안전 영역의 개수를 구하고, 최댓값으로 갱신하다.
- 0인 영역을 카운트 해서 반환한다.
static int getSafeZone(int[][] copyMap) {
int safeZone = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (copyMap[i][j] == 0) {
safeZone++;
}
}
}
return safeZone;
}
MAX = Math.max(MAX, safeZone); // 최댓값 갱신
3. 코드
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static int N;
static int M;
static int[][] map;
static int MAX = Integer.MIN_VALUE;
public static void main(String[] args) throws IOException {
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());
}
}
// 벽을 3개 생성하는 모든 방법을 구한다.(DFS)
dfs(0);
bw.write(MAX + "\n");
bw.flush();
bw.close();
}
static void dfs(int depth) {
if (depth == 3) {
int safeZone = bfs(); // BFS를 통해 감염 시킨다.
MAX = Math.max(MAX, safeZone);
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(depth + 1);
map[i][j] = 0;
}
}
}
}
static int bfs() {
Queue<Point> q = new LinkedList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 2) {
q.offer(new Point(i, j));
}
}
}
int[][] copyMap = new int[N][M];
for (int i = 0; i < N; i++) {
copyMap[i] = map[i].clone();
}
while (!q.isEmpty()) {
Point cur = q.poll();
for (int i = 0; i < 4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if (nx < 0 || nx >= N || ny < 0 || ny >= M || copyMap[nx][ny] != 0) {
continue;
}
q.offer(new Point(nx, ny));
copyMap[nx][ny] = 2;
}
}
return getSafeZone(copyMap); // 안전 영역 개수를 구한다.
}
static int getSafeZone(int[][] copyMap) {
int safeZone = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (copyMap[i][j] == 0) {
safeZone++;
}
}
}
return safeZone;
}
static class Point {
int x;
int y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}'Algorithm' 카테고리의 다른 글
| [백준] 1753. 최단경로 - JAVA (0) | 2025.09.23 |
|---|---|
| [백준] 13460. 구슬 탈출2 - JAVA (0) | 2025.09.18 |
| [백준] 3190. 뱀 -JAVA (0) | 2025.09.14 |
| [백준] 2178. 미로탐색 - JAVA (0) | 2025.09.10 |
| [Programmers] 입국심사(이분탐색) - JAVA (0) | 2025.09.07 |