[백준] 17141번 연구소2 문제 BFS로 풀어보기
1. 문제
자세한 문제의 사항은 위의 링크를 클릭하여 백준 사이트에서 확인해보자.
2. 풀이
먼저 이 문제에서는 바이러스를 최대 m개 놓을 수 있기 때문에 어떤 위치에 바이러스 m개를 배치할지를 결정해주어야 한다. 그러기 위해서 먼저 문제에서 2라고 표시된 부분에 바이러스를 놓을 수 있다고 했기 때문에 가능한 바이러스의 위치를 ArrayList에다 넣어주도록 하겠다 (나는 virus라는 이름의 ArrayList를 만들어주었다). 그런 다음에 2라고 표시된 부분은 벽이 아니므로 자유롭게 움직일 수 있기에, 다시 0으로 바꾸어준다. 이러면 바이러스 자리인지 빈칸 자리인지 구분이 되지 않지만 우리는 ArrayList에다 넣어주었기 때문에 문제가 없다.
다음으로 m개의 바이러스 자리를 결정하기 위해서 재귀함수를 사용해준다.
static void recur(int index, int cnt) {
if (index == virus.size()) {
if (cnt == m) {//m개를 다 결정한 경우
bfs();
}
} else {
int x = virus.get(index).x;
int y = virus.get(index).y;
a[x][y] = 3;
recur(index+1, cnt+1); //해당 배열의 위치에 바이러스를 놓기로 결정한 경우
a[x][y] = 0;
recur(index+1, cnt);//해당 배열의 위치에 바이러스를 놓지 않기로 결정한 경우
}
}위와 같은 재귀함수를 만들어주었다. 이런 식으로 재귀함수로 바이러스 m개의 위치를 결정해준다. 만약 마지막 바이러스의 위치에 도착했는데 cnt가 m개라면 m개의 바이러스 위치를 모두 결정해준 것이니 bfs 함수를 호출해주면 된다.
여기서 바이러스의 진짜 위치를 표시해주기 위해서 만약 해당 좌표에 바이러스가 놓인 것이라면 그 값을 3으로 바꾸어주는 추가 작업도 실시해준다.
이제 그러면 bfs 함수가 어떻게 구성되어있는지 보도록 하겠다. (variable이 헷갈린다면 먼저 이 글의 가장 하단의 전체 코드를 보고 오는 것이 더 이해가 빠를 수 있다 )
static void bfs() {
for (int i=0; i<n; i++) {
for(int j=0; j<n; j++){
d[i][j]=-1;
}
}
Queue<Pair> q = new LinkedList<>();
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (a[i][j] == 3) {
q.add(new Pair(i,j));
d[i][j] = 0;
}
}
}
while (!q.isEmpty()) {
Pair p = q.remove();
int x = p.x;
int y = p.y;
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(new Pair(nx, ny));
}
}
}
}
int cur = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (a[i][j] != 1) {
if (d[i][j] == -1) return;
if (cur < d[i][j]) cur = d[i][j];
}
}
}
if (ans == -1 || ans > cur) {
ans = cur;
}
}먼저 d라는 배열을 모두 -1로 초기화해준다. 그런 다음 바이러스의 위치를 모두 queue에다가 넣어준다. 만약 벽이 아니고 방문하지 않은 칸이라면 이를 다시 queue에 넣어두는 등 일반적으로 우리가 BFS를 구할 때 하는 행동을 해준다.
그런 다음에 d의 최댓값을 찾는 것이 사실상 이 문제에서 구하고자 하는 값이다. 따라서 모든 배열의 칸을 돌면서 현재의 ans가 iteration에서 돌아서 나온 최댓값보다 작다면 이를 새로 update시키는 과정을 거친다.
이렇게 모든 과정을 거치게 되면 우리는 문제에서 구하고자 하는 값을 얻을 수 있다. 아래는 Java로 구현한 전체 코드이다.
3. 코드
import java.util.*;
class Pair {
int x, y;
Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
static int[][] a;
static int[][] d;
static final int[] dx = {0,0,1,-1};
static final int[] dy = {1,-1,0,0};
static int n, m;
static ArrayList<Pair> virus = new ArrayList<>();
static int ans = -1;
static void bfs() {
for (int i=0; i<n; i++) {
for(int j=0; j<n; j++){
d[i][j]=-1;
}
}
Queue<Pair> q = new LinkedList<>();
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (a[i][j] == 3) {
q.add(new Pair(i,j));
d[i][j] = 0;
}
}
}
while (!q.isEmpty()) {
Pair p = q.remove();
int x = p.x;
int y = p.y;
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(new Pair(nx, ny));
}
}
}
}
int cur = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (a[i][j] != 1) {
if (d[i][j] == -1) return;
if (cur < d[i][j]) cur = d[i][j];
}
}
}
if (ans == -1 || ans > cur) {
ans = cur;
}
}
static void recur(int index, int cnt) {
if (index == virus.size()) {
if (cnt == m) {
bfs();
}
} else {
int x = virus.get(index).x;
int y = virus.get(index).y;
a[x][y] = 3;
recur(index+1, cnt+1);
a[x][y] = 0;
recur(index+1, cnt);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
a = new int[n][n];
d = 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) {
a[i][j] = 0;
virus.add(new Pair(i,j));
}
}
}
recur(0,0);
System.out.println(ans);
}
}