[백준] 14502번: 연구소(DFS, BFS, 완전탐색)

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

14502번: 연구소

 

코드

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 Point{
	int x;
	int y;
	Point(int x, int y){
		this.x = x;
		this.y = y;
	}
}

public class Main {
	public static int N, M;			// 지도 크기
	public static int map[][];		// 지도
	public static int virusMap[][];	// 지도 복사본
	public static int max = 0;		// 최대 영역갯수
	public static int[] dx = {0, -1, 0, 1};	// 동북남서 방향
	public static int[] dy = {-1, 0, 1, 0};

	/* 완전탐색 + 백트래킹으로 벽 3개 세우기 */
	public static void dfs(int count) {

		if(count == 3) {	// 기저사례: 벽 3개 세웠을경우
			bfs();
			return;
		}

		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j] == 0) {	// 빈공간 
					map[i][j] = 1;	// 벽으로 세우기
					dfs(count+1);	// dfs로 벽 3개를 세울때까지 반복
					map[i][j] = 0;	// 백트래킹으로 세운 벽 허물기
				}
			}
		}
	}

	
	/* 빈 칸(0)인 곳에 바이러스(2) 채우기 */
	public static void bfs() {
		virusMap = new int[N][M];

		// 이전의  map 복사하기
		for(int i=0; i<N; i++) 
			for(int j=0; j<M; j++) 
				virusMap[i][j] = map[i][j];	

		Queue<Point> q = new LinkedList<>();
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(virusMap[i][j] == 2) {
					q.add(new Point(i, j));
				}
			}
		}

		while(!q.isEmpty()) {
			Point p = q.poll();
			int x = p.x;
			int y = p.y;

			for(int i=0; i<4; i++) {	// 동북서남 4방향 탐색
				int nx = x + dx[i];
				int ny = y + dy[i];
				if(nx>=0 && ny>=0 && nx<N && ny<M) {	// map의 범위
					if(virusMap[nx][ny] == 0) {	// 빈공간 -> 바이러스로 퍼뜨린다.
						virusMap[nx][ny] = 2;
						q.add(new Point(nx, ny));
					}
				}
			}
		}
		max = checkVirusCount();		
	}

	
	/* 안전영역의 갯수 구하기 */
	public static int checkVirusCount() {
		int cnt = 0;
		for(int i=0; i<N; i++) 
			for(int j=0; j<M; j++)
				if(virusMap[i][j] == 0) 
					cnt ++;
		
		return Math.max(max, cnt);
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];

		for(int i=0; i<N; i++) {
			st = new StringTokenizer(bf.readLine());
			for(int j=0; j<M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j] == 0) {
					map[i][j] = 1;
					dfs(1);
					map[i][j] = 0;
				}
			}
		}

		System.out.println(max);
		bf.close();
	}
}

풀이

dfs + bfs + 완전탐색 + 백트래킹으로 푸는 문제다...

문제가 너무 어려워서 다른 블로그들을 참고했다.. 거의 구글에 Java 관련 포스팅은 다 본 것 같다.

문제 해결법은 다음과 같다.

 

 1) 완전탐색을 통해 map의 모든 곳에 벽을 3개를 세운다.

 2) 벽이 3개가 세워졌으면, 이제 map에 바이러스를 퍼뜨릴 수 있는곳에 모두 바이러스를 퍼뜨린다.

 3) 위 과정이 끝나면, 안전영역의 갯수를 구하고, 최대 갯수인지 비교한다.

 

풀이는 간단한데 아직 bfs나 백트래킹에 대한 이해가 완전하지가 않아서 이해하는데 힘들었다.

이전에 사용된 map을 사용할경우, 맵이 겹치고 중복되기때문에 바이러스로 채울때는 map을 새로 선언해야한다.

 

 

dfs나 백트래킹은 확실히 사용되는 로직은 비슷비슷 한 것 같다.

좀 더 많은 문제를 풀면서 이해하고 감을 익히는게 중요한 것 같다.