[백준] 14502.연구소 (java) / 백트래킹, DFS, BFS, 조합

@백트래킹, DFS, BFS, 조합 / 29m (필기 15m 포함)

기본 문제라서 무난하게 풀었다.

 

 

문제 링크

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

14502번: 연구소

 

 

구현 방법

이 문제는 빈 칸에 총 3개의 벽을 세우는 문제이다.

1. 여러 개의 빈 칸 중, 벽을 세울 3곳을 골라 벽을 세운다

2. 뱌이러스를 퍼뜨린다

3. 안전 영역의 수를 센다

이 순서대로 구현했다.

 

 

1. 벽을 세울 3곳을 고른다

이 부분에서, backTracking을 활용했다. 3곳을 뽑을 때 순열이 아닌 조합이기 때문에

재귀를 이용한 조합을 구현할 때 처럼 이전에 뽑은 위치의 다음 칸을 매개변수로 줬다.

이차원 배열이므로, 내가 지금 뽑은 칸인 (i, j)의 다음 칸인 (i, j + 1)부터 돌도록 구현했다.

 

백트래킹 개념 때문에 많이 헷갈렸는데, 이 문제는 조합을 이용한 재귀함수의 형태와 많이 닮았다고 생각하니 이해가 좀 쉬웠다.

단지 조합에서 뽑을 대상 배열의 형태가 1차원이 아니라 2차원이라고 생각하면 된다.

 

 

2. 바이러스를 퍼뜨린다.

BFS를 이용했는데, 이 때 바이러스를 매번 조합을 구할 때마다 새로 찾기가 번거로워서

1) 처음 입력받을 때 LinkedList에 바이러스 정보를 저장해 둔 뒤,

2) 바이러스를 퍼뜨리기 전에 Queue에 옮겨 담아서 사용했다.

 

 

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

public class Main {
	private static class Node {
		int x, y;
		Node (int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	private static int N, M, max = Integer.MIN_VALUE, map[][], copyMap[][];
	private static int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
	private static LinkedList<Node> virusList;
	private static Queue<Node> q;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		virusList = new LinkedList<Main.Node>();
		q = new LinkedList<Main.Node>();
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new int[N][M];
		copyMap = new int[N][M];
		
		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) virusList.add(new Node(i, j));
			}
		}
		
		backTraking(0, 0, 0);
		System.out.println(max);
	}

	private static void backTraking(int x, int y, int step) {
		if (step == 3) {
			copyMapMake();
			copyVirusQueue();
			spreadVirus();
			safeFieldCount();
			return;
		}
		
		for (int i = x; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (i == x && j < y) continue;
				
				if (map[i][j] == 0) {
					map[i][j] = 1;
					backTraking(i, j + 1, step + 1);
					map[i][j] = 0;
				}
			}
		}
	}

	private static void spreadVirus() {
		while (!q.isEmpty()) {
			Node temp = q.poll();
			
			for (int d = 0; d < 4; d++) {
				int nx = temp.x + dx[d];
				int ny = temp.y + dy[d];
				
				//map이 visit 역할을 대신 해줌 
				if (nx < 0 || nx >= N || ny < 0 || ny >= M || copyMap[nx][ny] != 0) continue;
				
				copyMap[nx][ny] = 1;
				q.add(new Node(nx, ny));
			}
		}
	}
	
	private static void copyVirusQueue() {
		for (int i = 0; i < virusList.size(); i++)
			q.add(virusList.get(i));
	}
	
	private static void safeFieldCount() {
		int count = 0;
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
				if (copyMap[i][j] == 0)
					count++;
		
		if (max < count) max = count;
	}

	private static void copyMapMake() {
		for (int i = 0; i < N; i++)
			copyMap[i] = map[i].clone();
	}
}

 

아래가 매개변수로 위치를 준 코드, 위는 안 주고 매번 (0, 0)부터 탐색한 코드

 

 

헷갈려서 이전에 뽑은 좌표를 주지 않고, 늘 (0, 0) 부터 탐색하게 했더니 시간이 거의 두 배가 들었다.

이유는 순열처럼 같은 조합을 여러 번 뽑아서 시간이 오래 걸렸다.

이 문제는 벽의 순서가 필요한 문제가 아니므로, 조합처럼 풀면 된다.

 

끝!