난이도

Gold 4

풀이 참고 유무

x

막힌 부분

x

문제

문제 바로가기

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.
빈 칸의 개수는 3개 이상이다.

출력

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

예제 입력

7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

예제 출력

27

문제 검토

1도 3개만 추가되고 연구실 범위가 적어서 완전 탐색이 가능해보인다.
허나 조금 더 효율적으로 백트랙킹을 사용해보겠다.

풀이(python)

Python

from collections import deque
from sys import stdin
def bfs(matrixx):    
    q=deque()        
    for x in virus:
        q.append(x)
    dx=[-1,1,0,0]    
    dy=[0,0,1,-1]
    while q:
        r,c=q.popleft()        
        for x in range(4):
            nr=r+dx[x]
            nc=c+dy[x]
            if nr>=n or nr<0 or nc>=m or nc<0:
                continue
            if matrixx[nr][nc]==2 or matrixx[nr][nc]==1:            
                continue            
            matrixx[nr][nc]=2
            q.append([nr,nc])
    a=checkSafe(matrixx)
    return a

            
def checkSafe(matrixxx):
    cnt=0
    for x in range(n):
        for y in range(m):
            if matrixxx[x][y]==0:
                cnt+=1
    return cnt                                
    
input=stdin.readline
n,m=map(int,input().split())
safe=[]
matrix=[list(map(int,input().split())) for _ in range(n)]
virus=[]

for x in range(n):
    for y in range(m):
        if matrix[x][y]==0:
            safe.append([x,y])
        if matrix[x][y] == 2:
            virus.append([x,y])
answer=0                  
import copy                     
def back(depth,idx):
    global answer    
    if depth == 3: 
        tmp=[mat[:] for mat in matrix]            
        answer=max(bfs(tmp),answer)                
        return
    for x in range(idx,len(safe)):
        matrix[safe[x][0]][safe[x][1]]=1
        back(depth+1,x+1)
        matrix[safe[x][0]][safe[x][1]]=0
back(0,0)
print(answer)

Java

import java.util.*;
import java.io.*;
public class Main{
    static int n,m;
    //행렬의 크기는 정해져 있으므로 2차원 배열
    static int matrix[][];
    static int matrixx[][];
    //safe나 virus는 입력 값에 따라 크기가 달라질 것이므로 int[]를 요소로 하는 Arraylist로 생성
    static ArrayList<int[]> safe;
    static ArrayList<int[]> virus;
    static int max;
    static int dx[]={-1,1,0,0};
    static int dy[]={0,0,-1,1};
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        //고정된 크기의 행렬에 배열 할당
        matrix=new int[n][m];
        matrixx=new int[n][m];
        //virus와 safe에 arraylist 할당
        virus = new ArrayList<>();
        safe = new ArrayList<>();
        //행렬 만들기
        for(int i=0; i<n;i++){
            for(int j=0; j<m; j++){
                int a=sc.nextInt();
                matrix[i][j]=a;
                matrixx[i][j]=a;
            }
        }
        //안전한 곳과 virus의 위치를 배열 형태로 append
        for(int i=0; i<n;i++){
            for(int j=0; j<m; j++){
                if (matrix[i][j]==0){
                    safe.add(new int[]{i,j});
                }
                if (matrix[i][j]==2){
                    virus.add(new int[]{i,j});
                }
            }
        }
        back(0,0);
        System.out.println(max);

    }
    public static int bfs(){
        //배열을 요소로 받는 큐 생성
        Queue <int[]> q=new LinkedList<>();
        for(int i=0; i<virus.size();i++){
            int tmp[]=virus.get(i);
            q.add(tmp);
        }
        while(!q.isEmpty()){
            int tmp[]=q.poll();
            int x=tmp[0];
            int y=tmp[1];
            for(int i=0; i<4;i++){
                int nx=x+dx[i];
                int ny=y+dy[i];
                if(nx<0 || nx>=n || ny <0 || ny>=m){
                    continue;
                }
                if(matrix[nx][ny]==2 || matrix[nx][ny]==1){
                    continue;
                }
                matrix[nx][ny]=2;
                q.add(new int[]{nx,ny});
            }
        }
        return checksafe();
    }
    public static int checksafe(){
        int cnt=0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(matrix[i][j]==0){
                    cnt+=1;
                }
            }
        }
        return cnt;
    }
    public static void back(int depth, int idx){
        if (depth==3){
            //새로운 matrix에 matrixx(원본) 행렬을 복사
            matrix=new int[n][m];
            for(int i=0;i<n;i++){
                for(int j=0; j<m;j++){
                    matrix[i][j]=matrixx[i][j];
                }
            }
            int tmp=bfs();

            if (tmp>max){
                max=tmp;
            }
            return;
        }
        for(int i=idx; i<safe.size();i++){
            int tmp[]=safe.get(i);
            //원본 배열의 벽을 조작
            matrixx[tmp[0]][tmp[1]]=1;
            back(depth+1,i+1);
            matrixx[tmp[0]][tmp[1]]=0;
        }
    }
}

아이디어:

#n=64 정도 된다.
#63c3 으로 백트랙킹을 떠올릴 수 있을 것 같다.
#안전한 좌표들을 다 저장하고 그 중 벽 3개를 골라서 bfs를 수행한다.

시간복잡도

#깊이가 깊어봤자 3이기 때문에 충분히 가능할 것 같다.
#63c3 은 41664이고 bfs는 대략 64464로 16385번의 연산수행횟수를 수행한다.
#41664 * 16385는 682,664,640 정도 되는데 시간 안에 해결이 어려울 수도 있겠다.

걸린 시간

31:21 - 파이썬 풀이 기준

총평

원래는 구현 문제라길래 구현 실력을 키우려고 했으나 이 문제를 보자마자 백트랙킹이 생각났는데 다른 백트랙킹 유형의 문제보다 비교적 쉽고 시간제한도 널널해서 오히려 Gold5 정도의 난이도라고 생각했다.

자바로 푸는 것이 쉽지는 않는데 크기가 정해져 있으면 배열을 사용하고 가변적인 데이터라면 ArrayList를 사용하는 것에 잘 적응하자.
또한 문자열 사용하는 것이 익숙하지 않으니 문자열 문제도 자바로 많이 접해보자.