[BOJ] 15812 - 침략자 진아

[백준] 15812 - 침략자 진아

접근

가장 단순하고 무식한 방법을 생각해보자. 두 개의 폭탄을 설치할 수 있는 모든 경우에 대해 BFS를 돌려보면서 최소시간을 갱신하면 되지 않을까? 맞다! N, M 이 최대 20으로 가능한 칸의 수는 400이고 두 개의 폭탄을 설치하는 경우의 수는 160,000 즉, 10⁵정도이다. 또한 한 번 BFS를 도는데 걸리는 시간은 2 x edge의 수 이므로 400 x 4 즉 10³이다 둘을 곱해도 10⁸이므로 주어진 시간 안에 수행할 수 있다!

추가 기재 사항

매번 강조해도 모자라지만 반드시 문제에 주어진 조건을 빠뜨리지 말자. 집이 있는 곳에 폭탄을 설치할 수 없다는 조건을 빼먹어서 틀렸습니다를 받았다.

소스코드

#include<iostream>
#include<limits.h>
#include<algorithm>
#include<queue>
#include<functional>
#include<string.h>
using namespace std;
typedef long long ll;
typedef tuple<int, int, int> T;

queue<T> q;
char map[25][25];
int n, m;
bool visited[25][25];
const int dr[4] = { 0, 0, 1, -1 }, dc[4] = { 1,-1,0,0 };

bool is_in_range(int x, int y) {
	return x >= 0 && x < n && y >= 0 && y < m;
}

int bfs() {
	int rtn = 1;
	memset(visited, 0, sizeof(visited));
	while (!q.empty()) {
		int xx = get<0>(q.front()), yy = get<1>(q.front()), c = get<2>(q.front());
		visited[xx][yy] = true;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int x = xx + dr[i], y = yy + dc[i];
			if (is_in_range(x, y) && !visited[x][y]) {
				q.push({ x, y, c + 1 });
				visited[x][y] = true;
				if (map[x][y] == '1')
					rtn = max(rtn, c + 1);
			}
		}
	}
	return rtn - 1;
}

int go(int x, int y, int cnt) {
	if (cnt == 2) {
		return bfs();
	}
	queue<T> tmp;
	tmp = q;
	int rtn = INT_MAX;
	for (int i = x; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == '1' || (i == x && j <= y)) continue;
			q = tmp;
			q.push({ i, j, 1 });
			rtn = min(rtn, go(i, j, cnt + 1));
		}
	}
	return rtn;
}

int main(void) {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%s", map[i]);
	}
	printf("%d", go(0, -1, 0));
	return 0;
}