Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- CS
- mst
- 문자열
- Kotlin
- 시뮬레이션
- 플로이드-와샬
- 백트래킹
- 구현
- 위상정렬
- 유니온 파인드
- 스택
- 수학
- 백준
- 프로그래머스
- 알고리즘
- swea
- Effective Java
- 후니의 쉽게 쓴 시스코 네트워킹
- java
- 동적계획법
- dfs
- BFS
- Network
- 그리디
- JUnit 5
- 이분탐색
- 투 포인터
- 에라토스테네스의 체
- 완전탐색
- 세그먼트 트리
Archives
반갑습니다!
[백준] 14502 연구소 본문
풀이
DFS와 BFS를 활용해서 해결하였다. 백트래킹으로 모든 경우의 벽을 세워보고, 벽을 3개 세웠을 경우에 BFS를 통해 빈 칸의 최대 넓이를 구하면 된다.
코드
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int n, m, blank, ans;
int map[8][8];
vector<pair<int, int>> virus;
vector<pair<int, int>> blanks;
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };
int bfs(int count) {
bool visited[8][8] = { false, };
queue<pair<int, int>> q;
// 큐에 바이러스를 모두 넣는다
for (auto v : virus) {
visited[v.second][v.first] = true;
q.push(v);
}
while (!q.empty()) {
int x = q.front().first; int y = q.front().second;
q.pop();
if (count < ans) return -1;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i]; int ny = y + dy[i];
if (nx < 0 || nx > m - 1 || ny < 0 || ny > n - 1) continue;
if (!visited[ny][nx] && map[ny][nx] == 0) {
count--;
q.push({ nx, ny });
visited[ny][nx] = true;
}
}
}
return count;
}
void dfs(int idx, int cnt) {
// 벽 3개를 다 세운 경우
if (cnt == 3) {
// 벽을 3개 세웠으므로 blank -3
ans = max(ans, bfs(blank - 3));
return;
}
// 백트래킹하면서 벽을 세운다
for (int i = idx + 1; i < blanks.size(); i++) {
int x = blanks[i].first; int y = blanks[i].second;
map[y][x] = 1;
dfs(i, cnt + 1);
map[y][x] = 0;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> map[i][j];
if (map[i][j] == 0) {
// 빈 칸 개수 미리 카운팅
blank++;
// 빈 칸 위치 저장
blanks.push_back({ j, i });
}
// 바이러스 위치 저장
if (map[i][j] == 2) virus.push_back({ j, i });
}
}
dfs(-1, 0);
cout << ans << '\n';
return 0;
}
'알고리즘 문제 풀이' 카테고리의 다른 글
[백준] 10156 과자 (0) | 2020.05.01 |
---|---|
[백준] 11404 플로이드 (0) | 2020.05.01 |
[백준] 2174 로봇 시뮬레이션 (0) | 2020.04.30 |
[백준] 3987 보이저 1호 (0) | 2020.04.30 |
[백준] 9655 돌 게임 (0) | 2020.04.29 |