[백준 14502] 연구소 (JAVA)
🔰 문제
💡 접근방식
시간 제한이 2초로 나름 널널한 편이다.
N, M 모두 3~8로 최대 8X8=64개의 칸을 갖는다. 64개의 칸이 전부 0이라 해도 벽 3개를 세우는 경우의 수는 64C3 = 약 4만이기에 일일이 다 세워보는 브루트 포스 방식 적용.
벽을 세운 뒤에 바이러스를 퍼뜨리는 것은 BFS로 실행
makeWall(int cnt, int start)
- 벽 3개 세우기 (0인 부분에서 3개의 좌표 고르기 - 순열)
spreadVirsus(int[][] map)
- 벽 3개 다 세웠으면, 바이러스 퍼뜨리기 (BFS)
getSafeArea(int[][] map)
- 바이러스 다 퍼졌으면 안전 영역 구하기 (2중 반복문)
💦 풀면서 실수, 놓친 점
- 0인 곳에서 벽 세울 3개 좌표를 구할 때 중복 순열 코드로 작성해버렸다. 디버깅하다가 알아채서 조합 코드로 수정하였다.
- 바이러스 퍼뜨릴 때 하나의 map에서 전부 실행하여, 첫번째 실행에서만 정상적인 안전 영역 구하고, 그 뒤부턴 첫번째에서 이미 퍼뜨린 map 상태에서 실행되어 정상적인 값 안 나왔다. -> 바이러스 퍼뜨리는 용의 map을 따로 만들어 spreadVirus 함수에 인자로 전달해줌.
🕑 소요시간
25분
예전에 풀 땐 어려워서 1시간 넘게 걸렸는데 다시 푸니 금방 풀었다. 실력이 오르는 것 같아 기분이 좋다!
💻 풀이
import java.io.*;
import java.util.*;
public class Main_14502 {
static int N, M;
static int map[][];
static boolean visited[][];
static List<int[]> list;
static int dx[] = { -1, 1, 0, 0 };
static int dy[] = { 0, 0, -1, 1 };
static int res; // 안전 영역 최대크기(정답)
public static void main(String[] args) throws Exception {
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];
list = new ArrayList<int[]>(); // 0인 곳 좌표 저장
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());
if (map[i][j] == 0)
list.add(new int[] { i, j });
}
}
// 벽 세우기 시작
makeWall(0, 0);
System.out.println(res);
}
private static void makeWall(int cnt, int start) {
if (cnt == 3) { // 벽 3개 다 세웠으면
visited = new boolean[N][M];
spreadVirus(map); // 바이러스 퍼뜨리기
return;
}
for (int i = start; i < list.size(); i++) {
int cur[] = list.get(i);
int cx = cur[0], cy = cur[1];
map[cx][cy] = 1; // 벽 세우기
makeWall(cnt + 1, i + 1);
map[cx][cy] = 0; // 벽 허물기
}
}
private static void spreadVirus(int[][] map) {
int newMap[][] = copy(map); // 바이러스 퍼뜨릴 map 새로 생성
Queue<int[]> q = new LinkedList<>();
// map 탐색하면서 바이러스 있는 곳(2) 전부 큐에 삽입
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (newMap[i][j] == 2) {
q.add(new int[] { i, j });
visited[i][j] = true;
}
}
}
while (!q.isEmpty()) {
int cur[] = q.poll();
int cx = cur[0], cy = cur[1];
for (int i = 0; i < 4; i++) {
int nx = cx + dx[i];
int ny = cy + dy[i];
if (nx < 0 || nx >= N || ny < 0 || ny >= M || visited[nx][ny] || newMap[nx][ny] == 1) // 범위 벗어났거나, 이미
// 방문했거나, 벽이면 패스
continue;
if (newMap[nx][ny] == 0) {
newMap[nx][ny] = 2; // 바이러스 퍼뜨리기
q.offer(new int[] { nx, ny });
visited[nx][ny] = true;
}
}
}
// 바이러스 다 퍼뜨렸으면 안전영역 구하기
getSafeArea(newMap);
}
private static int[][] copy(int[][] map) {
int[][] tmp = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
tmp[i][j] = map[i][j];
}
}
return tmp;
}
private static void getSafeArea(int[][] map) { // 안전 영역 구하기
int count = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 0)
count++;
}
}
res = Math.max(res, count); // 정답 갱신
}
}
🌟 비슷한 유형의 문제들
참고
Author And Source
이 문제에 관하여([백준 14502] 연구소 (JAVA)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bobae1998/백준-14502-연구소-JAVA저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)