백준 14502 (연구소) - java

https://www.acmicpc.net/problem/14502

14502번: 연구소

import java.io.*;
import java.util.*;
public class Main {
    static int[][] board= new int[9][9];
    static boolean[][] visit = new boolean[9][9];
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    static LinkedList<point> virus =  new LinkedList<>(); // 바이러스를 저장하는 리스트
    static int n = 0;
    static int m = 0;
    static int count = 0;
    static int re = 0;
    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());

        for(int i=1;i<=n;i++)
        {
            st = new StringTokenizer(br.readLine()," ");
            for(int j=1;j<=m;j++)
            {
                board[i][j] = Integer.parseInt(st.nextToken());
                if(board[i][j]==0) // 안전 범위를 구하기 위해 처음에 0의 개수를 구한다
                {
                    count++;
                }
                if(board[i][j]==2) // 바이러스의 경우 리스트에 추가
                {
                    virus.add(new point(i,j));
                }
            }
        }
        count = count-3; // 벽을 3개 쳐야하기 때문에 안전범위의 값 조정
        travel(0,1,1);
        System.out.println(re);
        br.close();
    }
    static int bfs() // 바이러스의 전염을 bfs로 나타낸다
    {
        boolean[][] visit2 = new boolean[9][9];
        int result = count;
        for(point e : virus) {
            visit2[e.x][e.y] = true;
        } 
        Queue<point> q = new LinkedList<>(virus); // 바이러스를 큐에 복사
        while(!q.isEmpty())
        {
            point cur = q.poll();
            for(int i=0;i<4;i++)
            {
                int nx = cur.x+dx[i];
                int ny = cur.y+dy[i];

                if(nx>=1&&nx<=n&&ny>=1&&ny<=m)
                {
                    if(board[nx][ny]==0&&!visit2[nx][ny]) // 방문하지 않았고 안전범위인 경우
                    {
                        visit2[nx][ny]=true; // 전염
                        result = result-1; // 안전 범위 축소
                        q.add(new point(nx,ny));
                    }
                }
            }
        }
        return result; // 모든 전염이 끝났을 때 안전 범위의 크기 반환
    }

    static void travel(int k,int row,int col)
    {
        if(k==3) // 벽을 3개 친 경우 : 해당 문제에서 탈출 조건
        {
            int re1 = bfs(); // 바이러스의 전염을 통한 안전 범위를 구한다
            if(re1>re)
            {
                re = re1; // 갱신
            }
            return;
        }

        if(col>m) // 열
        {
            row = row+1;
            col = 1;
        }

        if(row>n) // 행
        {
            return;
        }

        if(board[row][col]==0&&!visit[row][col]) // 해당 위치가 안전 범위인 경우
        {
            visit[row][col]= true;
            board[row][col]=1;
            travel(k+1,row,col+1); // 벽을 치는 경우
            visit[row][col]=false;
            board[row][col]=0;
            travel(k,row,col+1); // 벽을 치지 않는 경우
        }
        else if(board[row][col]!=0)
        {
            travel(k,row,col+1); // 안전 범위가 아닌 경우 위치 조정 
        }

    }
}
class point
{
    int x;
    int y;
    point(int x,int y)
    {
        this.x = x;
        this.y = y;
    }
}

바이러스의 전염 - BFS

벽을 3개 치면서 안전 범위를 확인하는 과정 - 백트랙킹

 

문제의 조건을 보면 빈 공간(벽을 칠 수 있는 공간)이 3개 이상이 무조건 주어진다. 그렇기 때문에 처음 행렬을 입력받는 과정에서 0의 개수를 세자 . 그런 후 해당 값에서 3을 뺀 다음 안전 범위를 구하면 불필요한 2중 반복문(아마 0의 개수를 구하는 거겠죠?)를 생략할 수 있다.