백준 17142번 연구소 3 C++ DFS, BFS, 완전 탐색

리뷰

 

어렵다고 생각이 들진 않았는데 생각보다 엣지케이스가 많아서 오답이 많이 노출되었다... 후

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

 

문제 풀이

1. n과 m을 입력 받고 맵 정보를 초기화 한다. 만약 맵에 2가 존재한다면 Pos구조체 타입의 virus 벡터에 추가해 준다.
2. 입력을 다 받고 나서 length 변수에 virus의 크기를 저장해 주고 dfs를 실행해 준다.
3. dfs를 통해 virus의 크기만큼의 반복을 돌며 중복이 없고 순서가 있는 탐색을 진행해 준다.
4. 기저조건은 level이 m이 도달했을 때이다, path 변수에 저장된 인덱스를 갖고 bfs를 실행해 준다.
5. 방문 배열부터 초기화 해준다, 이때 벽의 경우에는 미리 0으로 초기화 해주고 나머지는 -1로 초기화 해준다.
6. path에 저장된 인덱스를 갖는 virus 정보를 큐에 모두 추가해 주고, 현재 위치를 0으로 방문 처리해준다.
7. 현재 위치로부터 4방향 탐색을 진행하며, 방문하지 않았고, 벽이 아닌 모든 부분을 탐색해 준다.
8. 이때 활성화 되지 않은 바이러스를 방문할땐 거리를 0으로 체크해 주어야 한다.
9. 만약 현재 좌표의 방문값이 ans보다 크거나 같을 경우 더 이상 탐색해 줄 필요가 없다. 매우 큰 값 리턴
10. while이 종료되었다면 방문 배열에 -1 값이 존재하는지 체크해 준다. 있다면 역시 매우 큰 값을 리턴해 준다.
11. 벽이 아닌 모든 부분을 탐색했다면 가장 큰 값을 max_val 변수에 저장해둔 뒤 해당 값을 리턴해 주면 된다.
12. 매 탐색에서 bfs의 출력값을 ans의 최소값으로 갱신해 주고, 모든 탐색이 종료된 뒤 ans값을 출력해 주면 된다.

 

참고 사항

중복이 없고 순서가 있는 탐색을 할 경우엔 방문처리 및 이전값이 앞으로 올 값보다 커야 한다는 조건을 추가하면 된다.

예제 테스트케이스를 보니 선택한 바이러스가 아니라 해도 빈 칸으로 보지 않는다. 아래에 엣지케이스 몇개를 전달해 준다.

 

5 3
2 2 2 0 0
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
answer : 2

4 2
0 1 1 0
2 1 1 2
2 1 1 2
0 1 1 0
answer : 2

5 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
2 0 0 2 0
1 1 1 1 1
answer : 2

5 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
0 2 0 2 0
1 1 1 1 1
answer : 3

5 1
2 2 2 1 1
2 1 1 1 1
2 1 1 1 1
2 1 1 1 1
2 2 2 2 0
answer : 1

4 1
2 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
answer : 0

 

 

정답 코드

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;
int n, m, length, ans = 1e9;
int lst[50][50];
int visit[50][50];
int v[10] = { 0, };

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

struct Pos {
	int x, y, d;
};

vector<Pos> virus;

void init() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (lst[i][j] == 1) visit[i][j] = 0;
			else visit[i][j] = -1;
		}
	}
}

int bfs(vector<int>& path) {
	queue<Pos> q;
	init();
	for (int i = 0; i < m; i++) {
		Pos pos = virus[path[i]];
		q.push(pos);
		visit[pos.x][pos.y] = 0;
	}
	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y, cd = pos.d;
		if (visit[cx][cy] >= ans) return 1e9;
		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i], ny = cy + dy[i], nd = cd + 1;
			if (0 <= nx && nx < n && 0 <= ny && ny < n && visit[nx][ny] == -1 && lst[nx][ny] != -1) {
				if (lst[nx][ny] == 2) visit[nx][ny] = 0;
				else visit[nx][ny] = nd;
				q.push({ nx, ny, nd });
			}
		}
	}
	int max_val = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (visit[i][j] == -1 && !lst[i][j]) return 1e9;
			else max_val = max(max_val, visit[i][j]);
		}
	}
	return max_val;
}

void dfs(int level, vector<int>& path) {
	if (level == m) {
		ans = min(ans, bfs(path));
		return;
	}

	for (int i = 0; i < length; i++) {
		if (v[i]) continue;
		if (!path.empty() && i < path[level - 1]) continue;
		v[i] = 1;
		path.push_back(i);
		dfs(level + 1, path);
		path.pop_back();
		v[i] = 0;
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> lst[i][j];
			if (lst[i][j] == 2) virus.push_back({i, j, 0});
		}
	}
	length = virus.size();
	vector<int> path;
	dfs(0, path);
	if (ans == 1e9) cout << -1;
	else cout << ans;
}