[백준] 14502번
사이트
https://www.acmicpc.net/problem/14502
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크
www.acmicpc.net
문제
분석
- 필자가 그렇게 풀고 싶었던 문제를 풀었다... 그래프 문제를 하도 많이 풀어서 그래프 틀 알고리즘을 세우는 것은 어렵지 않았고 오히려 재밌었다!
- 하지만 벽을 무조건 3개 세우는 알고리즘을 도대체 어떻게 구현을 해야하는지 정말 많은 고민을 해왔다. 전체 경우의 수를 구해서 for 구문을 세울려고 했지만 이거는 너무 노가다일뿐더러 오히려 짜기 복자했고 bfs로 구현할라해도 좀 뭔가 안맞아서 고민을 했다... 결국 다른 분들꺼를 참고해서 분석해본결과 dfs 즉 재귀함수를 이용하면 된것이었다... 하지만 필자가 재귀함수 지식이 너무 부족해 힘들었다... 공부를 많이 해야겠다!
public class Graph14502 {
static int n;
static int m;
static int[][] arr;
static boolean[][] visited;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int max = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
arr = new int[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(0);
System.out.println(max);
}
입력 부분과 static 변수 선언은 늘 해왔던걸로 하면 된다. 이때 dfs(0)을 호출한다! 메소드명이 좀 그렇지만 dfs()는 벽을 세우기 위해 만든 것이다!
static void dfs(int wall) {
if (wall == 3) {
bfs();
return;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 0) {
arr[i][j] = 1;
dfs(wall + 1);
arr[i][j] = 0;
}
}
}
}- 필자가 많이 고민했던 문제의 알고리즘이다.
- 일단 0이 들어오므로 if문에는 안걸린다. 그후 arr 배열에서 0있으면 1로 바꾼뒤 wall+1해서 다시 dfs()를 호출한다.
- 그러면 wall이 1인 상태로 또 arr 배열에 0이있는지 확인한다. 이떄 처음 wall(0)에서 arr[0][0] 이 0일때 1이 됐으므로 wall(1)에서 arr[0][0]를 건너뛰고 arr[0][1] 이 0일때 1로 바꾼다. 그리고 또 wall(2)를 호출 ..... 그 후 wall(3)일때 if 문에 걸려 bfs()로 가게 된다.
static void bfs() {
visited = new boolean[n][m];
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 2) {
queue.add(new int[]{i, j});
}
}
}
int[][] copyArr = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
copyArr[i][j] = arr[i][j];
}
}
while (!queue.isEmpty()) {
int[] temp = queue.poll();
int staticX = temp[0];
int staticY = temp[1];
for (int i = 0; i < 4; i++) {
int nextX = staticX + dx[i];
int nextY = staticY + dy[i];
if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m) {
if (copyArr[nextX][nextY] == 0 && !visited[nextX][nextY]) {
visited[nextX][nextY] = true;
copyArr[nextX][nextY] = 2;
queue.add(new int[]{nextX, nextY});
}
}
}
}
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (copyArr[i][j] == 0) {
cnt++;
}
}
}
max = Math.max(max, cnt);
}- 이번 bfs() 함수는 좀 길다.. 하나하나 보자
visited = new boolean[n][m];
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 2) {
queue.add(new int[]{i, j});
}
}
}
일단 바이러스 전파를 위해 arr 배열에서 2가 있을때 queue에다가 담아준다.
int[][] copyArr = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
copyArr[i][j] = arr[i][j];
}
}
- 그 후 arr 배열을 망가뜨리지 않기 위해 copyarr에 깊은 복사를 한다. 이때 얕은 복사 즉 copyarr=arr이렇게 하게 되면
주소만 복사 되어 arr이 변경될떄 copy도 변경되서 안된다!!
while (!queue.isEmpty()) {
int[] temp = queue.poll();
int staticX = temp[0];
int staticY = temp[1];
for (int i = 0; i < 4; i++) {
int nextX = staticX + dx[i];
int nextY = staticY + dy[i];
if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m) {
if (copyArr[nextX][nextY] == 0 && !visited[nextX][nextY]) {
visited[nextX][nextY] = true;
copyArr[nextX][nextY] = 2;
queue.add(new int[]{nextX, nextY});
}
}
}
}
- 이거는 뭐 다들 잘 아시겠지만 바이러스를 전파하는 코드이다.
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (copyArr[i][j] == 0) {
cnt++;
}
}
}
max = Math.max(max, cnt);
그 후 전파가 끝났으면 copy에서 0 즉 안전구역을 세서 max랑 비교를 한다. 이때 max는 static으로 0으로 선언했기 떄문에
자연스럽게 비교가 된다. 그리고 이 bfs()함수 호출이 끝났으면
static void dfs(int wall) {
if (wall == 3) {
bfs();
return;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 0) {
arr[i][j] = 1;
dfs(wall + 1);
arr[i][j] = 0;
}
}
}
}
- 다시 일로와서 return;을 수행하게 된다. 그러면 wall(3)이 끝났으므로 arr[i][j]==0 이 수행하게 된다. 즉 arr[0][2] 가 0이 된다. 다시말해서 0으로 자동으로 바꿔준다. 그 후 for 구문에 따라서 또 0을 1만들고 dfs를 호출하게 되어 계속 반복하게 된다.
- 즉 재귀 함수가 모든 경우의 수를 만들어 놓기 때문에 우리가 일일히 경우의 수를 만들어 안돌려 된다.
전체 코드
package graph;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Graph14502 {
static int n;
static int m;
static int[][] arr;
static boolean[][] visited;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int max = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
arr = new int[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(0);
System.out.println(max);
}
static void dfs(int wall) {
if (wall == 3) {
bfs();
return;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 0) {
arr[i][j] = 1;
dfs(wall + 1);
arr[i][j] = 0;
}
}
}
}
static void bfs() {
visited = new boolean[n][m];
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 2) {
queue.add(new int[]{i, j});
}
}
}
int[][] copyArr = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
copyArr[i][j] = arr[i][j];
}
}
while (!queue.isEmpty()) {
int[] temp = queue.poll();
int staticX = temp[0];
int staticY = temp[1];
for (int i = 0; i < 4; i++) {
int nextX = staticX + dx[i];
int nextY = staticY + dy[i];
if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m) {
if (copyArr[nextX][nextY] == 0 && !visited[nextX][nextY]) {
visited[nextX][nextY] = true;
copyArr[nextX][nextY] = 2;
queue.add(new int[]{nextX, nextY});
}
}
}
}
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (copyArr[i][j] == 0) {
cnt++;
}
}
}
max = Math.max(max, cnt);
}
}
결과
느낀점
아 그 벽세우는 알고리즘때문에 오래걸렸다. 역시 골드 문제다... 재귀함수 즉 다이나믹 프로그래밍 코테문제를 이젠 집중적으로 풀어야겠다. 그래프는 이젠 너무 쉽다.