문제
내가 생각했을때 문제에서 원하는부분
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다.
2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.
빈 칸의 개수는 3개 이상이다.
첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.내가 이 문제를 보고 생각해본 부분
변수 선언 및 초기화 부분
N, M: 연구소 격자의 세로(N)와 가로(M) 크기를 저장한다.
lab: 연구소 격자를 2차원 배열로 표현한다.
각 칸은 0(빈 칸), 1(벽), 2(바이러스) 중 하나이다.
emptySpaces: 빈 칸 좌표를 저장하는 리스트이다.
벽을 세울 후보 칸을 이곳에 모아둔다.
virusPositions: 바이러스가 있는 위치 좌표 리스트이다.
BFS를 위해 시작점 역할을 한다.
maxSafeArea: 벽 3개를 세운 후 최대 안전 구역(바이러스가 못 퍼지는 빈 칸)의 크기를 기록한다.
dx, dy: 상하좌우 네 방향 탐색을 위한 배열이다.
main 메서드: 입력 처리 및 초깃값 세팅
표준 입력으로 N, M을 받고, 이후 각 행마다 줄을 읽어 격자 배열 lab에 상태를 저장한다.
빈 칸(0)은 벽을 세울 후보가 되므로 emptySpaces에, 바이러스(2)는 확산 시작점이므로 virusPositions에 각각 좌표를 저장한다.
buildWall 메서드: 재귀 백트래킹으로 벽 3개 세우기
count가 3이면 벽 3개를 모두 세운 상태로, 이때 바이러스 확산 시뮬레이션을 시작해준다.
아직 설치할 벽이 남았다면, 빈 칸 리스트에서 다음 위치부터 가능한 모든 칸에 벽을 세워 재귀 호출한다.
재귀 호출이 끝나면 탐색 과정에서 변경된 칸을 다시 빈 칸으로 복원한다.
이렇게 하면 모든 빈 칸 조합 중 3개 벽을 세우는 모든 경우를 검사할 수 있다.
spreadVirusAndCalculate 메서드: 바이러스 확산 시뮬레이션 및 안전 영역 계산
배열 복사: 원본 lab 배열을 복사하여 tempLab에 저장하고, 이 배열에서 바이러스 확산을 시뮬레이션한다.
원본을 건드리지 않기 위해 필요하다.
BFS 큐 초기화: 바이러스 위치를 큐에 넣고 BFS 시작 준비를 한다.
BFS 탐색: 큐에서 위치를 꺼내 상하좌우 인접한 칸을 검사한다.
빈 칸(0)이 있으면 바이러스(2)로 바꾸고 다시 큐에 추가해 퍼져나간다.
안전 영역 계산: 모든 확산이 끝나면 tempLab 배열에서 아직도 빈 칸(0)인 칸을 세어 안전 영역 크기를 구한다.
최대값 갱신: 이번 경우의 안전 영역이 이전 최대값보다 크면 maxSafeArea를 갱신해준다.
최종 결과 출력
buildWall 메서드가 모든 빈 칸 중 조합에 대해 탐색과 바이러스 퍼짐을 완료하면, maxSafeArea에는 가능한 최대 안전 영역 크기가 저장되어 있다.
main 함수 마지막에 그 값을 출력한다.
마지막에 리소스 누수를 막기 위해 br.close()로 스트림을 닫는다.코드로 구현
package baekjoon.baekjoon_33;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
// 백준 14502번 문제
public class Main1302 {
static int N, M;
static int[][] lab;
static ArrayList<int[]> emptySpaces = new ArrayList<>();
static ArrayList<int[]> virusPositions = new ArrayList<>();
static int maxSafeArea = 0;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
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());
lab = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j=0; j<M; j++) {
lab[i][j] = Integer.parseInt(st.nextToken());
if (lab[i][j] == 0) {
emptySpaces.add(new int[]{i, j});
} else if (lab[i][j] == 2) {
virusPositions.add(new int[]{i, j});
}
}
}
// 빈 칸에서 3개를 선택하여 벽 세우기
buildWall(0, 0);
System.out.println(maxSafeArea);
br.close();
}
static void buildWall(int start, int count) {
if (count == 3) { // 벽 3개 세우면 바이러스 퍼짐 시뮬레이션
spreadVirusAndCalculate();
return;
}
for(int i = start; i < emptySpaces.size(); i++) {
int[] pos = emptySpaces.get(i);
lab[pos[0]][pos[1]] = 1; // 벽 세우기
buildWall(i + 1, count + 1);
lab[pos[0]][pos[1]] = 0; // 원상복구
}
}
static void spreadVirusAndCalculate() {
int[][] tempLab = new int[N][M];
for (int i=0; i<N; i++) {
System.arraycopy(lab[i], 0, tempLab[i], 0, M);
}
Queue<int[]> queue = new LinkedList<>();
for(int[] v : virusPositions) {
queue.offer(v);
}
while(!queue.isEmpty()) {
int[] cur = queue.poll();
for (int dir=0; dir<4; dir++) {
int nx = cur[0] + dx[dir];
int ny = cur[1] + dy[dir];
if (nx >=0 && nx<N && ny>=0 && ny<M) {
if (tempLab[nx][ny] == 0) {
tempLab[nx][ny] = 2;
queue.offer(new int[]{nx, ny});
}
}
}
}
int safeCount = 0;
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
if (tempLab[i][j] == 0) safeCount++;
}
}
if (safeCount > maxSafeArea) {
maxSafeArea = safeCount;
}
}
}
마무리
코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.
Junior backend developer