[Algorithm] BOJ-14502 Java로 문제풀이 (완전탐색)

---

안녕하세요 Coding-Knowjam입니다.

오늘은 백준 온라인 저지에 있는 문제를 풀어보겠습니다.

문제에 대한 설명은 따로 하지 않으니, 문제를 직접 보고 오시길 바랍니다.

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

 

1. 문제 해설

• 난이도 : 골드 5
• 문제풀이 키워드 : 완전 탐색, BFS, 순열, 조합, 재귀

문제를 읽어보셔서 아시겠지만 목적은 기둥 3개를 빈 곳에 새로 심고 나서 바이러스가 퍼지지 않은 안전한 영역이 최대일 때의 값을 출력하는 것입니다.

그러면 우선 기둥 3개를 어떻게 심어야 안전한 영역의 개수가 최대가 될지를 고민해야 하는데, 문제의 조건 중 전체 영역의 크기가 최대 8 X 8 이므로 완전 탐색으로 해결해 볼 수 있습니다.

완전 탐색을 수행하기 위해 기둥이 심어지는 모든 경우의 수를 체크해봐야 하는데 기둥이 (1,0), (2,0), (3,0)에 심어지는 것과 (3,0), (2,0), (1,0)의 형태로 심어지는 것은 동일한 경우의 수라는 것을 기억해야 합니다.

즉, 기둥이 심어진 순서와 관계없이 위치만 같으면 동일한 경우의 수라고 체크해야 합니다. (수학으로 치면 조합입니다)

그럼 코드를 살펴보겠습니다.

 

2. 문제 풀이(Java)

우선 바이러스 클래스를 만들어주겠습니다.

	// 바이러스
	static class Virus {
		int row;	// 행
		int column;	// 렬

		// 생성자를 통해서 바이러스 위치 저장
		Virus(int row, int column) {
			this.row = row;
			this.column = column;
		}
	}

클래스 내부에 행과 열의 정보를 담을 변수를 만들어주고, 이를 통해 바이러스의 위치를 파악할 수 있습니다.

 

다음으로는 완전 탐색을 위해서 모든 경우의 수를 체크할 조합 메서들 만들어 주겠습니다.

메서드 내부에서 선언하지 않고 사용하는 변수들은 static변수로 클래스 내부에 선언한 것들입니다.

	// 조합(nCr)
	static void combination() {
		
		// 기둥이 3개 이상 심어졌을 경우
		if(count >=3) {
			// 바이러스가 퍼지는 경로를 계산하기 위해 기존영역과 동일한 새로운 영역 생성 및 초기화
			int[][] copyMap = new int[map.length][map[0].length];
			for (int i = 0; i < copyMap.length; i++) {
				for (int j = 0; j < copyMap[i].length; j++) {
					copyMap[i][j] = map[i][j];
				}
			}
			
			// BFS를 수행항 Queue 생성
			Queue<Virus> q = new LinkedList<>();
			// List에서 바이러스 객체 가져와서 큐에 넣기
			for (Virus virus : vl) {
				q.offer(virus);
			}
			
			// Queue가 빌 때 까지 반복
			while(!q.isEmpty()) {
				// Queue에서 바이러스 꺼내기
				Virus v = q.poll();
				// 현재 바이러스 위치 저장(행, 열)
				int r = v.row;
				int c = v.column;
				// 바이러스가 퍼져나갈 경로 계산 (상하좌우이므로 총 4번 반복)
				for (int i = 0; i < moveR.length; i++) {
					// 바이러스가 다음에 이동 할 좌표 계산
					int mr = r + moveR[i];
					int mc = c + moveC[i];
					// 다음에 이동 할 위치가 영역을 벗어나거나, 벽이거나, 이미 바이러스가 퍼진곳이라면 좌표 다시 계산
					if(mr < 0 || mr >= copyMap.length || mc < 0 || mc >= copyMap[0].length || copyMap[mr][mc] == 1 || copyMap[mr][mc] == 2) {
						continue;
					}else {
						// 영역을 벗어나지 않고, 빈 칸이면서, 바이러스가 퍼진 곳이 아니면 해당 위치에 바이러스 전파 및 Queue에 바이러스 넣기
						q.offer(new Virus(mr, mc));
						copyMap[mr][mc] = 2;
					}
				}
			}
			
			// 안전한 영역을 계산하기 위한 임시변수
			int temp = 0;
			// 안전한 영역 개수 계산
			for (int i = 0; i < copyMap.length; i++) {
				for (int j = 0; j < copyMap[i].length; j++) {
					if(copyMap[i][j] == 0) {
						temp++;
					}
				}
			}
			
			// 안전한 영역의 개수가 최대일 때 갱신
			if(temp > maxValue) {
				maxValue = temp;
			}
			
			// 종료
			return;
		}
		
		// 기둥이 2개 이하로 심어졌을 때 전체영역을 탐색하면서 빈 곳에 기둥 심기
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				if(map[i][j] == 0) {
					map[i][j] = 1;
					count++;
					combination();
					count--;
					map[i][j] = 0;
				}
			}
		}
	}

코드가 짧은 분량은 아니지만 주석에 설명을 전부 달아놓았으니 천천히 읽어보시기 바랍니다.

65 ~ 75라인의 코드가 기둥을 심는 모든 경우의 수를 구하는 부분입니다.

순서는 고려하지 않으므로 수학적으로는 조합을 구하는 거라 생각하시면 됩니다.

조합의 구현을 위해서 재귀 함수를 사용했고, 심은 기둥의 개수가 3개 이상일 때, 메서드는 종료되며 그 이후에는 기둥을 철거하고 다음 위치에 기둥을 다시 심어서 탐색한다고 이해하시면 될 것 같습니다.

사실 저는 처음에 이 부분을 구현하는데 많은 고민을 했습니다.

그래서 다른 사람들이 작성한 코드를 많이 봤었는데, 한 번에 이해가 되지 않아서 여러 번 봤었습니다.

여러분도 혹시 이해가 잘 되지 않으시면 값을 코드에 대입해가면서 천천히 동작 방식을 살펴보면 코드를 좀 더 수월하게 이해하실 수 있을 것입니다.

 

그럼 main메서드를 포함해서 전체 소스코드를 살펴보겠습니다.

package study.blog.codingnojam.algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BOJ_14502 {

	//전체 영역을 나타날 배열
	static int[][] map;
	// 기둥을 몇개 심었는지 체크 할 변수
	static int count = 0;
	// 현재 존재하는 바이러스들
	static List<Virus> vl = new ArrayList<>();
	// 바이러스 퍼지는 경로 계산을 위한 배열
	static int[] moveR = {1,-1,0,0};
	static int[] moveC = {0,0,1,-1};
	// 안전한 영역의 개수를 담을 변수
	static int maxValue = -9;
	
	public static void main(String[] args) throws IOException {
		// 문제를 풀기 위한 입력 값 받기 및 초기화
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] mapSize = br.readLine().split(" ");
		map = new int[Integer.parseInt(mapSize[0])][Integer.parseInt(mapSize[1])];
		for (int i = 0; i < map.length; i++) {
			String[] sTemp = br.readLine().split(" ");
			for (int j = 0; j < map[i].length; j++) {
				map[i][j] = Integer.parseInt(sTemp[j]);
				if(map[i][j] == 2) {
					// 영역 값 초기화하면서 현재 바이러스들 위치 체크
					vl.add(new Virus(i, j));
				}
			}
		}
		// 완전탐색 실행
		combination();
		// 값 출력
		System.out.println(maxValue);		
	}
	
	// 조합(nCr)
	static void combination() {
		// 기둥이 3개 이상 심어졌을 경우
		if(count >=3) {
			// 바이러스가 퍼지는 경로를 계산하기 위해 기존영역과 동일한 새로운 영역 생성 및 초기화
			int[][] copyMap = new int[map.length][map[0].length];
			for (int i = 0; i < copyMap.length; i++) {
				for (int j = 0; j < copyMap[i].length; j++) {
					copyMap[i][j] = map[i][j];
				}
			}
			
			// BFS를 수행항 Queue 생성
			Queue<Virus> q = new LinkedList<>();
			// List에서 바이러스 객체 가져와서 큐에 넣기
			for (Virus virus : vl) {
				q.offer(virus);
			}
			
			// Queue가 빌 때 까지 반복
			while(!q.isEmpty()) {
				// Queue에서 바이러스 꺼내기
				Virus v = q.poll();
				// 현재 바이러스 위치 저장(행, 열)
				int r = v.row;
				int c = v.column;
				// 바이러스가 퍼져나갈 경로 계산 (상하좌우이므로 총 4번 반복)
				for (int i = 0; i < moveR.length; i++) {
					// 바이러스가 다음에 이동 할 좌표 계산
					int mr = r + moveR[i];
					int mc = c + moveC[i];
					// 다음에 이동 할 위치가 영역을 벗어나거나, 벽이거나, 이미 바이러스가 퍼진곳이라면 좌표 다시 계산
					if(mr < 0 || mr >= copyMap.length || mc < 0 || mc >= copyMap[0].length || copyMap[mr][mc] == 1 || copyMap[mr][mc] == 2) {
						continue;
					}else {
						// 영역을 벗어나지 않고, 빈 칸이면서, 바이러스가 퍼진 곳이 아니면 해당 위치에 바이러스 전파 및 Queue에 바이러스 넣기
						q.offer(new Virus(mr, mc));
						copyMap[mr][mc] = 2;
					}
				}
			}
			
			// 안전한 영역을 계산하기 위한 임시변수
			int temp = 0;
			// 안전한 영역 개수 계산
			for (int i = 0; i < copyMap.length; i++) {
				for (int j = 0; j < copyMap[i].length; j++) {
					if(copyMap[i][j] == 0) {
						temp++;
					}
				}
			}
			
			// 안전한 영역의 개수가 최대일 때 갱신
			maxValue = Math.max(temp, maxValue);
			
			// 종료
			return;
		}
		
		// 기둥이 2개 이하로 심어졌을 때 전체영역을 탐색하면서 빈 곳에 기둥 심기
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				if(map[i][j] == 0) {
					map[i][j] = 1;
					count++;
					combination();
					count--;
					map[i][j] = 0;
				}
			}
		}
	}

	// 바이러스
	static class Virus {
		int row;	// 행
		int column;	// 렬

		// 생성자를 통해서 바이러스 위치 저장
		Virus(int row, int column) {
			this.row = row;
			this.column = column;
		}
	}
}

 

main메서드 안에서는 입력 값을 받아서 초기화하는 부분 말고는 특별한 부분은 없습니다.

감사합니다.

---