[Baekjoon] 백준 14502 연구소 (G4 / DFS, BFS) - Java

링크

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

14502번: 연구소

 

 

 

 

문제 해석

- 문제 정의
연구소 크기 N*M
바이러스가 인접한 칸으로 퍼져 나갈 수 있음
벽으로 막히면 바이러스가 퍼지지 않으며, 퍼지지 않은 
벽을 3개 세웠을 때 바이러스가 퍼지지 않는 최대 영역 개수 구하기

 

1 벽
2 바이러스


- 입력
첫 번째 줄 : N M  # 세로 가로
나머지 줄  : 지도


- 출력
안전영역의 최대 크기

 

 

 

 

풀이 & 코드 해석

각각의 알고리즘은 쉽지만 여러 알고리즘을 혼합해서 사용해야하는 문제입니다.

 

완전 탐색을 통해서 벽 3개를 쌓는 경우의 수를 모두 찾고, 안전지역의 범위를 세는 방식으로 구현하였습니다.

벽을 쌓을 위치를 정하는 것은 DFS를 통해서 정하도록 만들었습니다.

 

벽을 모두 쌓았다면 BFS를 통해서 바이러스가 퍼지도록 하였습니다.

 

바이러스가 모두 퍼지고 났다면 0인 부분을 count하여 최종적으로 안전지역의 개수를 count 하였습니다.

 

 

 

 

코드

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

public class 연구소 {

	static int[][] map;
	static int[][] mapCopy;
	static Queue<Point> q;
	static Queue<Point> qCopy;
	static int answer;

	static class Point {
		int x;
		int y;

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

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		// 첫 번째 줄
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		map = new int[N][M];
		q = new LinkedList<>();
		qCopy = new LinkedList<>();
		answer = 0;

		// 나머지 줄
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 2) {
					q.offer(new Point(i, j));
				}
			}
		}

//		print(map);

		dfs(0);
		System.out.println(answer);

	}

	private static void dfs(int cnt) {
		// basis
		// 벽이 3개라면
		if (cnt == 3) {
			mapCopy = new int[map.length][map[0].length];
			copyMap(map, mapCopy);
			copyQ(q, qCopy);

			bfs();

			return;
		}

		// inductive
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				if (map[i][j] == 0) {
					map[i][j] = 1;
					dfs(cnt + 1);
					map[i][j] = 0;
				}
			}
		}
	}

	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };

	private static void bfs() {
		while (!qCopy.isEmpty()) {
			Point p = qCopy.poll();

			for (int d = 0; d < dx.length; d++) {
				int nx = p.x + dx[d];
				int ny = p.y + dy[d];
				if (nx >= 0 && nx < map.length && ny >= 0 && ny < map[0].length && mapCopy[nx][ny] == 0) {
					mapCopy[nx][ny] = 2;
					qCopy.offer(new Point(nx, ny));
				}
			}
		}

		int nowAnswer = 0;
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				if (mapCopy[i][j] == 0) {
					nowAnswer += 1;
				}
			}
		}
		if (answer < nowAnswer) {
			answer = nowAnswer;
//			print(mapCopy);
//			System.out.println("===================");
		}
	}

	private static void copyQ(Queue<Point> q, Queue<Point> qCopy) {
		for (int i = 0; i < q.size(); i++) {
			Point p = q.poll();
			q.offer(p);
			qCopy.offer(p);
		}

	}

	private static void copyMap(int[][] map, int[][] mapCopy) {
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				mapCopy[i][j] = map[i][j];
			}
		}
	}

	private static void print(int[][] map) {
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}

	}
}

 

 

 

 

발생한 문제 & 해결 방안

mapCopy를 사용해야하는데 map을 사용해서 자꾸 값이 제대로 안나오는 현상이 발생하였다.

 

코드 짤 때 정신차리고 짜기..

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java