<유사문제>
3055 탈출 https://www.acmicpc.net/problem/3055
5427 불 https://www.acmicpc.net/problem/5427
7576 토마토 https://www.acmicpc.net/problem/7576 (2차원)
7569 토마토 https://www.acmicpc.net/problem/7569 (3차원)
4179 Fire! https://www.acmicpc.net/problem/4179
2573 빙산 https://www.acmicpc.net/problem/2573
2636 치즈 https://www.acmicpc.net/problem/2636
8068 Water https://www.acmicpc.net/problem/8068
1. 백조의 호수
50%넘기면서 계속 틀리길래 솔루션으로 정답후
다른 사람 코드보고 틀린부분 수정해서 맞은 문제...
백조의 위치 L에서 인접한 빙판도 녹는다는것을 간과했다.
1. 백조의 위치, 물의 위치를 Queue에 넣고 bfs를 돌리며 빙판이 녹는시점을 저장해놓는다.
2. (0, max(빙판 녹는시점))구간을 백조끼리 만나는지 bfs를 돌리며 이분탐색 한다.
행,열이 50이나 100이하면 모든경우에대해 bfs를 차례대로 돌리면 되지만
큰 수가 주어지면 위와같이 시간을 줄일 필요가 있다.
#include <cstdio>
#include <queue>
using namespace std;
int N, M;
char map[1501][1501];
int L[2][2], lcnt = 0;
int dy[4] = { -1, 0, 0, 1 }, dx[4] = { 0, 1, -1, 0 };
int visit[1501][1501] = { 0 };
int water[1501][1501];
void clear(int arr[1501][1501]){
for (int n = 0; n < N; n++)
for (int m = 0; m < M; m++)
arr[n][m] = 0;
}
int waterbfs(){
int cnt = 1;
int ret = 0;
queue<pair<int, int>> q;
for (int n = 0; n < N; n++)
for (int m = 0; m < M; m++)
if (map[n][m] == '.' || map[n][m] == 'L') {
visit[n][m] = 1;
q.push({ n, m });
}
while (!q.empty()){
int sz = q.size();
for (int s = 0; s < sz; s++){
int y = q.front().first, x = q.front().second;
q.pop();
for (int i = 0; i < 4; i++){
int ny = y + dy[i], nx = x + dx[i];
if (ny < 0 || ny >= N || nx < 0 || nx >= M || visit[ny][nx]) continue;
if (map[ny][nx] != 'L'){
water[ny][nx] = cnt;
visit[ny][nx] = 1;
q.push({ ny, nx });
}
}
}
cnt++;
}
return cnt - 2;
}
bool bfs(int limit){
queue<pair<int,int>> q;
q.push({ L[0][0], L[0][1] });
visit[L[0][0]][L[0][1]] = 1;
while (!q.empty()){
int y = q.front().first, x = q.front().second;
q.pop();
if (y == L[1][0] && x == L[1][1]) return true;
for (int i = 0; i < 4; i++){
int ny = y + dy[i], nx = x + dx[i];
if (ny < 0 || ny >= N || nx < 0 || nx >= M || visit[ny][nx]) continue;
if (water[ny][nx] <= limit){
q.push({ ny, nx });
visit[ny][nx] = 1;
}
}
}
return false;
}
int main(){
scanf("%d%d", &N, &M);
for (int n = 0; n < N; n++){
for (int m = 0; m < M; m++){
scanf(" %1c", &map[n][m]);
if (map[n][m] == 'L'){
L[lcnt][0] = n;
L[lcnt++][1] = m;
}
}
}
int st = 0, en;
en = waterbfs();
while (st <= en){
clear(visit);
int mid = (st + en) / 2;
if (bfs(mid)) en = mid - 1;
else st = mid + 1;
}
printf("%d\n", st);
return 0;
}
| cs |
4종류의 Queue를 만들고 물과 거위에 대해 bfs를 돌리는건
같지만 초기화해서 하지않고 이어서 bfs를 돌린다.
#include <cstdio>
#include <queue>
using namespace std;
int N, M;
char map[1500][1500];
int L[2][2], lcnt = 0;
int wvisit[1500][1500], svisit[1500][1500];
queue<pair<int, int>> water, nwater;
queue<pair<int, int>> swan, nswan;
int main(){
int dy[4] = { -1, 0, 0, 1 }, dx[4] = { 0, 1, -1, 0 };
scanf("%d%d", &N, &M);
for (int n = 0; n < N; n++){
for (int m = 0; m < M; m++){
scanf(" %1c", &map[n][m]);
if (map[n][m] == 'L'){
L[lcnt][0] = n;
L[lcnt++][1] = m;
map[n][m] = '.';
}
if (map[n][m] == '.'){
water.push({ n, m });
wvisit[n][m] = 1;
}
}
}
swan.push({ L[0][0], L[0][1] });
svisit[L[0][0]][L[0][1]] = 1;
int ans = 0;
for (ans = 0; !svisit[L[1][0]][L[1][1]]; ans++){
for (; !water.empty(); water.pop()) nwater.push(water.front());
for (; !swan.empty(); swan.pop()) nswan.push(swan.front());
for (; !nwater.empty(); nwater.pop()){
int y = nwater.front().first, x = nwater.front().second;
map[y][x] = '.';
for (int i = 0; i < 4; i++){
int ny = y + dy[i], nx = x + dx[i];
if (ny < 0 || ny >= N || nx < 0 || nx >= M || wvisit[ny][nx]) continue;
wvisit[ny][nx] = 1;
water.push({ ny, nx });
}
}
for (; !nswan.empty(); nswan.pop()){
int y = nswan.front().first, x = nswan.front().second;
for (int i = 0; i < 4; i++){
int ny = y + dy[i], nx = x + dx[i];
if (ny < 0 || ny >= N || nx < 0 || nx >= M || svisit[ny][nx]) continue;
svisit[ny][nx] = 1;
if (map[ny][nx] == '.') nswan.push({ ny, nx });
else if (map[ny][nx] == 'X') swan.push({ ny, nx });
}
}
}
printf("%d\n", ans - 1);
return 0;
}
| cs |
2. 치즈
공기에 대해 bfs를 돌려주면서 치즈속 구멍인지 판별해주는 처리를 해준다.
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int N, M;
int map[101][101];
int visit[101][101];
bool cheeze[101][101];
int dy[] = { -1,0,0,1 }, dx[] = { 0,1,-1,0 };
int ans1 = 0, ans2 = 0;
void bfs(int iy, int ix, int group) {
bool isBlock = true;
bool tmp[101][101];
queue<int> q, chz;
memset(tmp, 0, sizeof tmp);
q.push(iy*M + ix);
visit[iy][ix] = group;
while (!q.empty()) {
int y = q.front() / M, x = q.front() % M;
q.pop();
for (int i = 0;i < 4;i++) {
int ny = y + dy[i], nx = x + dx[i];
if (ny < 0 || ny >= N || nx < 0 || nx >= M) {
isBlock = false;
continue;
}
if (!map[ny][nx] && !visit[ny][nx]) { //빈 공간
visit[ny][nx] = group;
q.push(ny*M + nx);
}
if (map[ny][nx] && !cheeze[ny][nx] && !tmp[ny][nx]) { // 치즈
chz.push(ny*M + nx);
tmp[ny][nx] = true;
}
}
}
if (isBlock) {
while (!chz.empty()) chz.pop();
}
else {
while (!chz.empty()) {
int ny = chz.front() / M, nx = chz.front() % M;
chz.pop();
cheeze[ny][nx] = true;
}
}
}
bool erase(int prev_cnt) {
int cnt = 0;
for (int n = 0;n < N;n++)
for (int m = 0;m < M;m++)
if (cheeze[n][m]) map[n][m] = 0, cnt++;
if (prev_cnt == cnt) return false;
else if (cnt) return true;
else return false;
}
bool solve() {
int g = 1;
ans2 = 0;
memset(visit, 0, sizeof visit);
memset(cheeze, 0, sizeof cheeze);
for (int n = 0;n < N;n++)
for (int m = 0;m < M;m++)
if (map[n][m]) ans2++;
if (ans2 == 0) return true;
ans1++;
for (int n = 0;n < N;n++) {
for (int m = 0;m < M;m++) {
if (!visit[n][m] && !map[n][m]) {
bfs(n,m,g);
++g;
}
}
}
if (erase(ans2)) return false; //지우는데 성공했으면 계속 돌림
else return true; //더이상 지울게 없거나 딱 맞춰 지웠을 경우 종료시킴
}
int main() {
scanf("%d%d", &N, &M);
for (int n = 0;n < N;n++)
for (int m = 0;m < M;m++)
scanf("%d", &map[n][m]);
while (1) {
if (solve())
break;
}
printf("%d\n%d\n", ans1, ans2);
return 0;
}
| cs |
3. Water
다음 그림과 같이 물이 차면 얼마나 차는지를 계산하는 문제이다.
가장자리를 제외하고 bfs를 돌리면서 시작지점 보다 낮은 지점으로 이동한다.
둘레 또한 시작지점보다 크면서 가장 최소의 높이를 구한다.
만약 이지점이 가장자리에 도달하면 물은 담기지 않는곳이다.
도달하지 않았으면 방문한 지점마다 최소의 높이만큼 물이 찬다.
[1, 1] (높이 1)은 바로 3으로 차고
[2, 5] (높이 1)는 2가 최소 높이이므로 2로 바뀐다.
[2, 6] (높이 2)에서 돌릴때 최소 높이인 3으로 두 지점이 바뀐다.
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 111111
using namespace std;
int N, M, G = 0;
int dy[] = { -1, 0, 0, 1 }, dx[] = { 0, 1, -1, 0 };
int map[100][100];
int ans = 0;
int visit[100][100];
void bfs(int iy, int ix){
int limit = map[iy][ix];
int lar = INF;
bool f = false;
queue<pair<int, int>> q;
vector<pair<int, int>> pos;
++G;
q.push({ iy, ix });
visit[iy][ix] = G;
pos.push_back({ iy, ix });
while (!q.empty()){
int y = q.front().first, x = q.front().second;
q.pop();
if (y == 0 || y == N - 1 || x == 0 || x == M - 1){
f = true; break;
}
for (int i = 0; i < 4; i++){
int ny = y + dy[i], nx = x + dx[i];
if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
if (map[ny][nx] <= limit && visit[ny][nx] < G){
visit[ny][nx] = G;
q.push({ ny, nx });
pos.push_back({ ny, nx });
}
if (map[ny][nx] > limit)
lar = min(lar, map[ny][nx]);
}
}
if (!f){
for (auto i : pos){
ans += lar - map[i.first][i.second];
map[i.first][i.second] = lar;
}
}
}
int main(){
scanf("%d%d", &N, &M);
for (int n = 0; n < N; n++)
for (int m = 0; m < M; m++)
scanf("%d", &map[n][m]);
for (int n = 0; n < N; n++){
for (int m = 0; m < M; m++){
if (n == 0 || n == N - 1 || m == 0 || m == M - 1) continue;
bfs(n, m);
}
}
printf("%d\n", ans);
return 0;
}
| cs |
