[백준 17142] 연구소3(JAVA/C++)

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

17142번: 연구소 3

작년에 C++로 풀었던 문제이다. JAVA로 다시 풀어봤는데 spread함수에서 return 조건 위치를 잘못생각해서 틀렸다.

입력받을때 빈공간을 emptySpace++로 카운트해놓고 시작했다. 바이러스를 놓을 수 있는 공간을 조합(select함수)으로 M개를 뽑은 다음 바이러스를 확산(spread()함수)시켜주었다. bfs를 턴마다 큐사이즈만큼 돌렸고 빈공간으로 확신 시킨 count횟수가 emptySpace와 같아질 때 바로 리턴해주었다.

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

public class Main {
	static class Pos {
		int x;
		int y;

		public Pos(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

	}

	static int[][] map;// 0빈칸, 1벽, 2바이러스 놓을수 있는 위치
	static boolean[][] visit;
	static boolean[] chk;
	static int[] dx = { 0, 0, 1, -1 };
	static int[] dy = { 1, -1, 0, 0 };
	static int N, M, ans = 987654321, emptySpace = 0;// 연구소크기, 바이러스개수
	static List<Pos> list = new ArrayList<Pos>();// 바이러스 후보
	static List<Pos> picked = new ArrayList<Pos>();// 바이러스 고른거

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

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 0) {
					emptySpace++;
				}
				if (map[i][j] == 2) {
					list.add(new Pos(i, j));
				}
			}
		} // 입력끝
		if (emptySpace == 0)
			System.out.println(0);
		else {
			chk = new boolean[list.size()];
			select(0);
			spread();
			System.out.println(ans == 987654321 ? -1 : ans);
		}
	}

	private static void select(int index) {
		if (picked.size() == M) {
			// M개 다 놓음
			spread();
			return;
		}
		if (index == list.size()) {
			return;
		}
		for (int i = index; i < list.size(); i++) {
			if (!chk[i]) {
				chk[i] = true;
				picked.add(new Pos(list.get(i).x, list.get(i).y));
				select(i + 1);
				picked.remove(picked.size() - 1);
				chk[i] = false;
			}
		}

	}

	private static void spread() {
		visit = new boolean[N][N];
		Queue<Pos> q = new LinkedList<Pos>();

		for (Pos p : picked) {
			q.offer(p);
		}
		int count = 0;
		int time = 1;
		while (!q.isEmpty()) {
			int qSize = q.size();
			while (qSize-- > 0) {
				Pos p = q.poll();
				for (int i = 0; i < 4; i++) {
					int nx = p.x + dx[i];
					int ny = p.y + dy[i];
					if (nx < 0 || ny < 0 || nx >= N || ny >= N || visit[nx][ny] || map[nx][ny] == 1)
						continue;
					visit[nx][ny] = true;
					if (map[nx][ny] == 0)
						count++;
					if (count == emptySpace) {
						if (ans > time)
							ans = time;
						return;
					}

					q.offer(new Pos(nx, ny));
				}
			}

			time++;
		}

	}

}

 

 

[C++]

 

#include <iostream>//6:18~
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int N, M, ans=987654321;
int emptySpace=0;
int map[50][50];
bool visited[50][50] = { 0, };
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };


vector <pair<int, int> > virus, picked;

bool IsAnswer() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 1)continue;
			if (visited[i][j] == false) return 0;
		}
	}
	return 1;
}
void Spread() {
	memset(visited, 0, sizeof(visited));
	queue <pair<int, int> > q;
	for (int i = 0; i < picked.size(); i++) {
		visited[picked[i].first][picked[i].second] = true;
		q.push(picked[i]);
	}
	int time = 0;
	int remain = emptySpace;
	while (!q.empty()) {
		if (remain ==0) {
			if (ans > time)ans = time;
			return;
		}
		int qSize = q.size();
		while (qSize--) {
			int x = q.front().first;
			int y = q.front().second;
			q.pop();
			//if (map[x][y] == 0) remain--;
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (nx < 0 || ny < 0 || nx >= N || ny >= N ||
					visited[nx][ny] || map[nx][ny] == 1)
					continue;
				visited[nx][ny] = true;
				if (map[nx][ny] == 0) remain--;

				q.push({ nx,ny });

			}
		}
		time++;
		//cout << time << " ";
		
		
	}
}
void Select(int index) {
	if (picked.size() == M) {
		//M개 뽑았을 경우 리턴
		Spread();
		return;
	}
	if (index == virus.size()) {
		return;
	}
	picked.push_back(virus[index]);
	Select(index + 1);
	picked.pop_back();
	Select(index + 1);
}
int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 0) {
				emptySpace++;
			}
			if (map[i][j] == 2) {
				virus.push_back({ i,j });
			}
		}
	}
	Select(0);
	if (ans == 987654321) {
		cout << -1;
	}
	else {
		cout << ans;
	}
	return 0;
}