[백준] BOJ 16000 섬

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

 

 

| Solved.ac 난이도 : P2 |

 

문제 추천도 : 6/10

 

 

🏷️ 그래프 이론, 탐색

 단절점을 이용한 풀이도 있다고 한다. 하지만 단순 그래프 탐색 풀이보다 어렵다고 봄.

 

 

풀이

 

1. $($상하좌우 네방향으로$)$ 이어져있는 육지들을 각각의 그룹으로 묶어준다.

 

2. 최외곽에는 항상 바다가 주어지므로 $($0,0$)$에서부터 바다를 탐색한다.

• 육지를 지나갈 수 없는 벽으로 보고 갈 수 있는 바다를 탐색한다.
• 상하좌우+4개의 대각선 방향으로 탐색한다.
  ⭐ KeyPoint -  대각선 방향은 어떤 육지를 거쳐 바깥쪽 바다로 가는 경우이다.
• 아래는 대각선 방향으로 안쪽 바다 -> 육지 -> 바깥쪽 바다로 가는 경우를 설명한다.

< 경우 1 >

바다	바다	바다	바다	바다	바다	바다
바다	육지	육지	육지	육지1	바다2	바다
바다	육지	바다	바다	바다1	육지2	바다
바다	육지	바다	육지 (현위치)	바다	육지	바다
바다	육지	바다	바다	바다	육지	바다
바다	육지	육지	육지	육지	육지	바다
바다	바다	바다	바다	바다	바다	바다

• < 경우 1 >에서는 가운데 육지에서 바다1을 거쳐 바다2로 갈 수 없다. $($육지1과 육지2가 같은 그룹이므로 같은 그룹의 육지를 반드시 지나야 하기 때문$)$ 따라서 이 경우는 가운데 육지가 안전한 땅이 아니다.

 

< 경우 2 >

바다	바다	바다	바다	바다	바다	바다
바다	육지	육지	육지	육지1	바다2	바다
바다	육지	바다	바다	바다1	육지2	바다
바다	육지	바다	육지 (현위치)	바다	육지	바다
바다	육지	바다	바다	바다	육지	바다
바다	바다	육지	육지	육지	육지	바다
바다	바다	바다	바다	바다	바다	바다

• 하지만 위와 같은 < 경우 2 >에서는 육지1과 육지2가 다른 그룹에 속하므로$($ㄱ자 육지와 ㄴ자 육지는 인접하지 않음$)$ 최외곽 바다로 나갈 수 있게 된다.
• 이 경우만 잘 판별해주면 나머지 구현은 어려울 것이 없다.

3. 지날 수 있는 바다를 탐색하며 만나게 되는 육지 그룹을 기록한다.

 

4. 이때 기록된 육지 그룹은 모두 어느 특정한 땅 하나를 무조건 지나지 않고 최외곽 바다로 갈 수 있는, 즉 안전한 땅이 된다.

 

 

---

 

 

구현
라이트 모드로 보셔야 잘 보입니다

풀이를 이해하셨다면 구현은 직접 자신의 결로 써보시길 추천드립니다.

# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define fastio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
int X[10]={-1,0,1,0,-1,1,1,-1};
int Y[10]={0,1,0,-1,1,1,-1,-1};
string s[2010];
int landch[2010][2010];
int waterch[2010][2010];
int safety[2000*2000];
int n,m;
int cnt;
void land_dfs(int x,int y)
{
    landch[x][y]=cnt;
    for(int i=0;i<4;i++)
    {
        int nx=x+X[i],ny=y+Y[i];
        if(nx<0 || ny<0 || nx>=n || ny>=m) continue;
        if(s[nx][ny]=='#' && landch[nx][ny]==0) land_dfs(nx,ny);
    }
}
void water_dfs(int x,int y)
{
    waterch[x][y]=1;
    for(int i=0;i<8;i++)
    {
        int nx=x+X[i],ny=y+Y[i];
        if(nx<0 || ny<0 || nx>=n || ny>=m) continue;
        if(i<4 && s[nx][ny]=='#') safety[landch[nx][ny]]=1;
        else if(i>=4 && s[nx][ny]=='.' && waterch[nx][ny]==0 && s[nx][y]=='#' && s[x][ny]=='#' && landch[nx][y]!=landch[x][ny]) water_dfs(nx,ny);
        else if(i<4 && s[nx][ny]=='.' && waterch[nx][ny]==0) water_dfs(nx,ny);
    }  
}
int main()
{
    fastio;
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>s[i];
    
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(s[i][j]=='#' && landch[i][j]==0)
            {
                cnt++;
                land_dfs(i,j);
            }
        }
    }
    water_dfs(0,0);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(s[i][j]=='.') cout<<'.';
            else if(safety[landch[i][j]]) cout<<'O';
            else cout<<'X';
        }
        cout<<'\n';
    }
}