[백준] 17142번: 연구소 3문제 BFS로 풀기
1. 문제
문제는 위 링크에 들어가서 볼 수 있다.
2. 풀이
이 문제는 먼저 바이러스를 놓을 수 있는 칸에서부터 시작해 바이러스를 m개 놓아야 한다. 그것을 우리는 재귀함수 move로 구현하겠다. 항상 그랬듯이, index와 count를 parameter로 받고 정해진 지점에 도달했을 때, 우리는 bfs를 돌리면서 검사를 하는 것이다.
move의 함수는 아래와 같다.
static ArrayList<Integer> xs = new ArrayList<>();
static ArrayList<Integer> ys = new ArrayList<>();
public static void move(int index,int count){
if (index==xs.size()){
if (count==m){
bfs();
}
}else{
int x = xs.get(index);
int y = ys.get(index);
a[x][y] = 3; //바이러스 놓기
move(index+1, count+1);
a[x][y] = 2;
move(index+1, count);
}
}여기서 xs는 가능한 바이러스의 위치를 알려주는 ArrayList이다. 문제에서 입력받을 때 바이러스를 놓을 수 있는 위치의 행을 xs에, 열을 ys에 저장한다. 그러면 index의 위치가 xs의 size와 같다는 것은 전체 바이러스를 다 검사했다는 것이고, 그 중에서 count의 값이 m이라는 것은 문제의 조건과 일치한다는 뜻이므로 그 때 bfs 함수를 호출해 bfs 검사를 해주면 된다.
static void bfs(){
int d[][]=new int[n][n];
Queue<Integer>q=new LinkedList<>();
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
d[i][j] = -1;
if (a[i][j] == 3) {
q.add(i);q.add(j);
d[i][j] = 0;
}
}
}
while(!q.isEmpty()){
int x=q.remove();
int y=q.remove();
for(int k=0; k<4; k++){
int nx=x+dx[k];
int ny=y+dy[k];
if (0<=nx && nx<n && 0<=ny && ny<n){
if (a[nx][ny] != 1 && d[nx][ny] == -1) {
d[nx][ny] = d[x][y] + 1;
q.add(nx); q.add(ny);
}
}
}
}
int val = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (a[i][j] == 0) { //이미 빈칸이었던 애들만 검사
if (d[i][j] == -1) return;
if (val < d[i][j]) val = d[i][j];
}
}
}
if (ans == -1 || ans > val) {
ans = val;
}
}위 코드는 bfs 함수만 적어본 것이다. 일반적인 BFS 코드와 유사하나 다른 점은 문제에서 빈칸이 바이러스에 감염되는 시간을 검사하라고 했으므로 원래 칸이 빈칸이었는지를 하나 더 검사해주어야 한다.
3. 풀이
전체 JAVA 코드를 살펴보면 아래와 같다.
import java.util.*;
public class Main{
static int[][] a;
static int[][] d;
static int[] dx = {0,0,1,-1};
static int[] dy = {1,-1,0,0};
static int n, m;
static ArrayList<Integer> xs = new ArrayList<>();;
static ArrayList<Integer> ys = new ArrayList<>();;
static int ans = -1;
static void bfs(){
d=new int[n][n];
Queue<Integer>q=new LinkedList<>();
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
d[i][j] = -1;
if (a[i][j] == 3) {
q.add(i);q.add(j);
d[i][j] = 0;
}
}
}
while(!q.isEmpty()){
int x=q.remove();
int y=q.remove();
for(int k=0; k<4; k++){
int nx=x+dx[k];
int ny=y+dy[k];
if (0<=nx && nx<n && 0<=ny && ny<n){
if (a[nx][ny] != 1 && d[nx][ny] == -1) {
d[nx][ny] = d[x][y] + 1;
q.add(nx); q.add(ny);
}
}
}
}
int val = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (a[i][j] == 0) { //이미 빈칸이었던 애들만 검사
if (d[i][j] == -1) return; //불가능
if (val < d[i][j]) {val = d[i][j];}
}
}
}
if (ans == -1 || ans > val) {
ans = val;
}
}
public static void move(int index,int count){
if (index==xs.size()){
if (count==m){
bfs();
}
}else{
int x = xs.get(index);
int y = ys.get(index);
a[x][y] = 3; //바이러스 놓기
move(index+1, count+1);
a[x][y] = 2;
move(index+1, count);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
a = new int[n][n];
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
a[i][j] = sc.nextInt();
if (a[i][j] == 2) {
xs.add(i);
ys.add(j);
}
}
}
move(0,0);
System.out.println(ans);
}
}