[ 문제 ]

[ 구현 ]
벽을 3군데 세우는 부분은 dfs + backtracking으로 처리하고,벽이 세워진 이후에 bfs로 넘어가서 바이러스가 퍼트려지도록 시뮬레이션을 돌리고 안전한 구역의 최대를 저장해두는 식으로 풀었다.
[ 코드 ]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int n, m;
static int[][] map;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int[] dx = {-1, 0, 0, 1};
static int[] dy = {0, -1, 1, 0};
static int answer = 0;
private static class Node {
int x, y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
private static void readInput() throws IOException {
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());
}
}
}
private static int calSafe(int[][] arr) {
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 0) {
cnt++;
}
}
}
return cnt;
}
private static void bfs() {
Queue<Node> q = new LinkedList<>();
int[][] map_copy = new int[n][m];
for (int i = 0; i < n; i++) {
map_copy[i] = map[i].clone();
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map_copy[i][j] == 2) {
q.offer(new Node(i, j));
}
}
}
while (!q.isEmpty()) {
Node 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 || ny < 0 || nx >= n || ny >= m) continue;
else if (map_copy[nx][ny] == 1 || map_copy[nx][ny] == 2) continue;
else {
map_copy[nx][ny] = 2;
q.offer(new Node(nx, ny));
}
}
}
answer = Math.max(answer, calSafe(map_copy));
}
private static void dfs(int depth) {
if (depth == 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(depth + 1);
map[i][j] = 0;
}
}
}
}
private static void solution() throws IOException {
readInput();
dfs(0);
System.out.println(answer);
}
public static void main(String[] args) throws IOException{
solution();
}
}
[ 마무리 및 느낀 점 ]
전체적으로 풀어야할 흐름자체는 직관적인 편이라 풀이과정을 떠올리는데 어렵지는 않았다.단지 아직 dfs + backtracking 부분에서 좀 자신이 없는 듯하여 관련 부분을 따로 연습하는 것이 좋아보인다.좀 더 사고력을 요하는 골드3 이상의 문제를 풀기 시작해야겠다.
'Algorithm > 백준' 카테고리의 다른 글
| [백준/java] 14499번 - 주사위 굴리기 (1) | 2025.09.26 |
|---|---|
| [백준/java] 1757번 - 달려달려 (2) | 2025.08.28 |
| [백준/java] 2539번 - 모자이크 (3) | 2025.08.14 |
| [백준/c++] 31230번 - 모비스터디 (0) | 2024.02.20 |
| [백준/c++] 1956번 - 운동 (0) | 2024.02.19 |