백준 14502번 - 연구소

 

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

14502번: 연구소

 

 

해당 문제는 DFS(Depth-First Search)와 BFS(Breadth-First Search) 알고리즘을 한번에 사용하는 대표적인 문제이다.

 

해당 문제를 풀기에 앞서 어떤식으로 풀어야할지 계획을 자보자.

1. 벽을 3개 세워줘야함.

2. 벽이 세워진 상태에서 바이러스를 퍼뜨려야함

3. 바이러스가 다 퍼진 map 에서 안전영역을 구해야함.

4. 각 경우마다 안전영역이 최대일때 개수를 출력.

 

 

1. 벽을 3개 세워줘야함. => DFS 사용

map 안에서 벽을 적당히 3개 세워줬을때 안전영역이 가장 많아지는 경우의 안전영역 개수를 구하는 것이므로,

DFS 알고리즘을 사용하여 벽을 3개 세워줘야 한다.

 

예를들어 아래와 같은 map 이 있다고 해보자

위의 map 에서 벽 3개를 세워주는 방법론은 아래와 같다.(새로운 벽은 편의상 3이라고 표기하자.)

즉, 위와 같이 순서대로 3개씩 계속 채워져가는 방법을 채택하면 된다.

위의 로직은 아래와 같이 구현하면 된다.

 

import java.io.*;

public class Main
{
	static int N,M;
	static int[][] map;
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		
		String[] colRow = br.readLine().split(" ");
		N = Integer.parseInt(colRow[0]);
		M = Integer.parseInt(colRow[1]);
		
		map = new int[N][M];
		
		for (int i = 0; i < N; i++) {
		    String[] inputs = br.readLine().split(" ");
		    
		    for (int j = 0; j < M; j++) {
		        map[i][j] = Integer.parseInt(inputs[j]);
		    }
		}//for
		
		dfs(0,0);
		
	}
	
	//dfs 알고리즘
	static void dfs(int cnt,int index) {
	    
	    //벽 3개를 세웠으면 중지.
	    if (cnt == 3) {
	        printMap();
	        return;
	    }

	    for (int i = 0; i < N*M; i++) {
	    	if (map[i/M][i%M] == 0) {
	    		map[i/M][i%M] = 3;
	    		dfs(cnt+1,i);
	    		map[i/M][i%M] = 0;
	    	}
	    }

	    
	}
	
	//map 표시
	static void printMap() {
	    System.out.println("=========================");
	        
	   for (int i = 0; i < N; i++) {
	       for (int j = 0; j < M; j++) {
	           System.out.print(map[i][j] + " ");
	       }
	       System.out.println();
	    }
	}
}

 

확인해보면 우리가 위에서 차례로 벽을 3개씩 세워주던 로직이 맞음을 알 수 있다.

 

 

2. 벽이 세워진 상태에서 바이러스를 퍼뜨려야함 => BFS 로직 사용

벽을 차례대로 3개씩 세워주는 로직을 만들어줬다면, 다음은 해당 벽이 세워졌을 경우에 바이러스가 퍼지는 양상을 

로직으로 짜야한다. 바이러스가 퍼지는 로직은 BFS 알고리즘을 사용하면되는데, 로직은 아래와 같다.

위와 같은 방식으로 벽이 세워진 후에 map 을 탐색하면서 해당칸이 바이러스인 경우(=2) 인접 칸이 비어진 칸(=0) 

인 경우 해당 칸을 바이러스칸 으로 바꾼다(바이러스 증식) 즉, 아래와 같이 변하게 되는 것이다.

 

 

이런식으로 map 에 있는 모든 바이러스칸에 대해서 인접한칸을 확인해주고 바이러스를 증식시켜주면 된다.

 

위의 로직은 아래와 같은 순서대로 생각하면 된다.

 

1. 행렬 위치에 대한 정보를 담을 수 있는 Queue를 생성해준다.

2. map 을 돌면서 바이러스인 칸의 행과 열 위치 정보를 Queue 에 담아준다.

3. Queue 의 size 가 0이 될때까지 루프문을 돌려서 바이러스인 위치정보를 받아온다.

4. 바이러스에 해당하는 칸에 인접한 칸을 비교하여 빈칸인 경우 바이러스칸으로 변환해주고(2로 변경)

   또한 해당 행렬 위치정보를 Queue에 담아준다.

 

3. 바이러스가 다 퍼진 map 에서 안전영역을 구해야함.

위에서 예시로 제시한 map의 경우 바이러스가 다 퍼진 이후에는 loop 문을 돌려서 해당칸의 값이 0 일때마다 카운트를

해준다. 

 

4. 각 경우마다 안전영역이 최대일때 개수를 출력.

벽이 3개 세워질때마다 바이러스를 퍼뜨려서 안전영역을 카운트 해주는데, 각 케이스마다 안전영역의 갯수를 비교해서

가장 큰 안전영역의 개수를 출력해준다.

 

 

즉, 이 문제의 전체로직은 아래와 같다.

 

1. JAVA

import java.io.*;
import java.util.*;

public class Main {
	
	static int[][] map;
	static int N,M;
	static int maxCount = 0;
	static int[] dx = {0,0,-1,1};
	static int[] dy = {1,-1,0,0};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] inputs = br.readLine().split(" ");
		
		N = Integer.parseInt(inputs[0]);
		M = Integer.parseInt(inputs[1]);
		
		map = new int[N][M];//지도 초기화
		
		//지도내에 벽,공백,바이러스 넣어주기
		for (int i = 0; i < N; i++) {
			String[] vals = br.readLine().split(" ");
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(vals[j]);
			}
		}
		
		dfs(0,0);
		
		bw.write(maxCount + "");
		bw.close();
		br.close();
		
	}
	
	static void dfs(int cnt, int index) {
		
		if (cnt == 3) {
			bfs();
			return;
		}
		
		for (int i = index; i < N*M; i++) {
			if (map[i/M][i%M] == 0) {
				map[i/M][i%M] = 1;
				dfs(cnt+1,i);
				map[i/M][i%M] = 0;
			}
		}
		
	}
	
	static void bfs() {
		Queue<int[]> queue = new LinkedList<int[]>();
		int[][] virusMap = new int[N][M];//map 행렬 복사
		
		
		for (int i = 0; i < N*M; i++) {
			virusMap[i/M][i%M] = map[i/M][i%M];
			if (virusMap[i/M][i%M] == 2) {
				int[] cor = {i/M,i%M};
				queue.offer(cor);
			}
		}
		
		while(!queue.isEmpty()) {
			int[] pair = queue.poll();
			int x = pair[0];
			int y = pair[1];
			
			for (int i = 0; i < 4; i++) {
				int newX = x + dx[i];
				int newY = y + dy[i];
				
				if (newX >= 0 && newY >= 0 && newX < N && newY < M && virusMap[newX][newY] == 0) {
					virusMap[newX][newY] = 2;
					queue.offer(new int[]{newX,newY});
				}
			}
		}
		
		int count = 0;
		
		for (int i = 0; i < N*M; i++) {
			if(virusMap[i/M][i%M] == 0) count++;
		}
		
		maxCount = Math.max(maxCount, count);
		
	}
	
	
	
	
}

 

 

2. C++

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef struct {
    int x,y;
} nods;

void dfs(int index,int cnt);
void bfs();

int N,M;
int max_count = 0;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int** map;

int main()
{
    scanf("%d %d", &N, &M);

    map = new int*[N];
    for (int i = 0; i < N; i++) map[i] = new int[M];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%d",&map[i][j]);
        }
    }

    dfs(0,0);

    printf("%d",max_count);

    return 0;
}

void dfs(int index, int cnt) {
    if (cnt == 3) {
        bfs();
        return;
    }

    for (int i = index; i < N*M; i++) {
        if (map[i/M][i%M] == 0) {
            map[i/M][i%M] = 1;
            dfs(i,cnt+1);
            map[i/M][i%M] = 0;
        }
    }
}

void bfs() {
    queue<nods> q;
    int** v_map = new int*[N];

    for (int i = 0; i < N; i++) v_map[i] = new int[M];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            v_map[i][j] = map[i][j];
            if (v_map[i][j] == 2) q.push({i,j});
        }
    }


    while(!q.empty()) {
        nods nd = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = nd.x + dx[i];
            int ny = nd.y + dy[i];

            if (nx >= 0 && ny >= 0 && nx < N && ny < M && v_map[nx][ny] == 0) {
                v_map[nx][ny] = 2;
                q.push({nx,ny});
            }
        }
    }

    int count = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (v_map[i][j] == 0) count++;       
        }
    }

    max_count = max(count,max_count);

    for(int i=0; i<N; i++) {
        delete[] v_map[i];
    }
    
    delete[] v_map;


}