[백준] 14502번 - "연구소" (Java)

www.acmicpc.net/problem/14502

14502번: 연구소

 

---

 

- 난이도 : 골5

dfs와 bfs를 공부를 조금 했다면 충분히 풀 수 있는 문제라고 생각합니다. dfs, bfs 둘 다 활용해서 풀 수 있고 dfs만 활용하여 풀 수도 있습니다. 

 

간단하게 먼저 설명하자면, 재귀 호출을 이용하여 map 배열을 탐색하며 벽을 3개 세웁니다. 탐색은 map 배열로 하지만, 바이러스 퍼트리기는 copy 배열로 진행합니다. 벽을 3개 세웠으면, bfs 탐색을 통해 바이러스를 퍼트립니다. 퍼트린 바이러스들을 바탕으로 안전지대를 세줍니다. 

 

 

- class dot {}

bfs탐색을 위하여 큐의 자료형 역할을 해줄 dot 클래스입니다. 매개변수로는 y, x (y축, x축)가 있습니다.

 

- void main()

전역 변수와 입력들을 초기화 및 선언하여 줍니다. 그런 다음 makeWall(0,0) 함수를 호출하고 문제를 해결한 다음 정답(ans)을 출력합니다. 

 

여기서 전역 변수인 q(큐)를 선언해줍니다. 큐를 전역 변수로 한 이유는 코드 구현 초기에 spreadVirus() 함수에서 while문을 돌기 전 매번 q를 만들고 선언해준 다음, 이중 배열을 통해 바이러스들을 q에 삽입하는 방식으로 구현하였습니다. 

 

하지만 생각해보니 매 번 같이 호출되는 copy() 함수에서도 이미 이중 배열을 돌고 있었고, 중복된다는 느낌을 받아 조금이라도 시간을 줄이기(?) 위해 기존 spreadVirus()에서 q 선언을 삭제하고 main문에서 선언 및 q 작업을 copy() 함수에서 진행하였습니다.  

 

- void makeWall(int start, int depth) 

depth가 곧 벽의 개수입니다. 저는 항상 재귀 문제를 풀 때 매개 변수를 depth로 선언하는 습관이 있습니다. 벽의 개수가 3개가 되면 바이러스 퍼트리기를 위한 copy 배열을 copy() 함수를 통해 만들어줍니다. copy 배열로 spreadVirus() 함수를 호출하고, 호출을 마친 copy 배열로 countSafe() 함수를 호출하여 안전지대 개수를 세주고 return 합니다. 

 

반복문은 2차원 배열 대신 1차원 배열로 구현하여 진행하였습니다. 왜냐하면 1차원 배열이 재귀 호출하는 데 좀 더 편하기 때문입니다. 

 

- void spreadVirus()

bfs를 활용하여 바이러스를 퍼트립니다. 상, 하, 좌, 우 방향으로 탐색하고 바이러스가 점령할 수 있는 곳이 있으면(copy [][] == 0) 전염시키고(copy [][] == 2) q(큐)에 집어넣습니다.

 

- int countSafe()

안전지대 개수를 세주고 그 갯수를 반환합니다. 

 

- void copy()

벽을 3개 세웠으면 그 map 배열을 copy 배열에 복사합니다. 그 이유는 매 번 탐색마다 바이러스의 개수는 달라지므로, 초기 입력을 받은 배열이 아닌 다른 복사된 배열로 진행하는 것이 좋습니다. 

 

  코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

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

public class BOJ_14502 {
	// BOJ / 14502번 / 연구소 / 그래프 / 골드5
	
	static int y,x, ans;
	static int map[][], copy[][];
	static int dy[] = {1,-1,0,0};
	static int dx[] = {0,0,-1,1};
	static Queue<dot> q;
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
		y = Integer.parseInt(stk.nextToken());
		x = Integer.parseInt(stk.nextToken());
		
		map = new int[y][x];
		copy = new int [y][x];
		q = new LinkedList<>();
		for(int i=0; i<y; i++) {
			stk = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<x; j++) {
				map[i][j] = Integer.parseInt(stk.nextToken());
			}
		}

		makeWall(0,0);
		System.out.println(ans);
	}
    
	// 재귀 호출을 통하여 벽을 3개 세웁니다. map 배열을 통해 탐색하고 바이러스는 copy 배열로 퍼트립니다.
	public static void makeWall(int start, int depth) {
		if(depth == 3) {
			copy();
			spreadVirus();
			ans = Math.max(ans, countSafe());
			return;
		}
        
		// 2차원 배열 1차원 배열로 변환.
		for(int i=start; i< y * x; i++) {
			int dy = i / x;
			int dx = i % x;
			if(map[dy][dx] == 2 || map[dy][dx] == 1) continue;
			
			map[dy][dx] = 1;
			makeWall(i+1,depth+1);
			map[dy][dx] = 0;
		}
	}
    
	// bfs로 바이러스틑 퍼트립니다. 
	public static void spreadVirus() {
		while(!q.isEmpty()) {
			dot now = q.poll();
			for(int i=0; i<4; i++) {
				int ny = now.y + dy[i];
				int nx = now.x + dx[i];
				
				if(ny >=0 && ny <y && nx <x && nx>=0) {
					if(copy[ny][nx] == 0) {
						copy[ny][nx] = 2;
						q.offer(new dot(ny,nx));
					}
				}
			}
		}
	}
    
	// 안전지대 갯수를 세줍니다. 
	public static int countSafe() {
		int count = 0;
		for(int i=0; i<y; i++) {
			for(int j=0; j<x; j++) {
				if(copy[i][j] == 0) {
					count++;
				}
			}
		}
		return count;
	}
    
	// map 배열을 copy배열에 복사합니다.
	public static void copy() {
		for(int i=0; i<y; i++) {
			for(int j=0; j<x; j++) {
				copy[i][j] = map[i][j];
                // 복사와 동시에 q에 바이러스 위치를 집어넣습니다.
				if(copy[i][j] == 2) q.offer(new dot(i,j));
			}
		}
	}
}

 

 

피드백은 얼마든지 환영합니다.