Week 7 - DFS+BFS

<>

Week 7 : DFS+BFS

[2146] 다리 만들기 (http://boj.kr/2146) 

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
 
struct P { int r, c; };
 
int n;
int g[101][101];
int checked[101][101];
 
int dr[]={1, 0, -1, 0};
int dc[]={0, 1, 0, -1};
 
int min(int a, int b)
{
    return a < b ? a : b;
}
 
bool safe(int r, int c)
{
    return (0 <= r && r < n) && (0 <= c && c < n);
}
 
void dfs(queue<P> &q, int r, int c, int cnt)
{
    g[r][c] = cnt;
 
    for(int k=0; k<4; k++) {
        int nr = r+dr[k];
        int nc = c+dc[k];
        if(safe(nr, nc)) {
            if(g[nr][nc] == 1) { 
                dfs(q, nr, nc, cnt);
            }
            else {// g[nr][nc] == 0
                if(!checked[nr][nc]) {   
                    q.push((P){nr, nc});
                    checked[nr][nc] = 1;
                }
            }
        }
    }
}
 
int bfs(queue<P> &q, int cnt)
{
    while(!q.empty()) {
        int curR = q.front().r;
        int curC = q.front().c; q.pop();
 
        for(int k=0; k<4; k++) {
            int nr = curR + dr[k];
            int nc = curC + dc[k];
            if(safe(nr, nc) && g[nr][nc] != cnt && !checked[nr][nc]) {
                checked[nr][nc] = checked[curR][curC]+1;
                q.push((P){nr, nc});
                if(g[nr][nc] != 0) {
                    return checked[curR][curC];
                }
            }
        }
    }
    return 1e9;
}
 
int main()
{
    scanf("%d", &n);
 
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            scanf("%d", &g[i][j]);
 
    int cnt = 1;
    int ans = 1e9;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(g[i][j] == 1) {
                cnt++;
 
                queue<P> q;
                dfs(q, i, j, cnt); 
 
                int tmp = bfs(q, cnt);
                ans = min(ans, tmp);
 
                memset(checked, 0, sizeof(checked));                
            }                
        }
    }
    printf("%d\n", ans);
}

>> 일단 하나의 섬을 하나의 컴퍼넌트로 체크를 하고, 섬 주위의 바다(0) 을 큐에 담는다.

>> 큐에 담긴 바다를 시작으로 거리를 잰다. 이때 현재섬이 아닌 섬을 만난 경우, 현재섬으로부터의 최소거리가 되므로 그 거리를 리턴한다.

>> 현재섬에는 cnt 값이 들어있다.

[]

[2573] 빙산 : http://boj.kr/2573 

#include <cstdio>
#include <queue>
using namespace std;
 
struct P { int r, c; };
struct M { int r, c, cnt; };
 
int r, c;
int g[301][301];
int dr[] = {1, 0, -1, 0};
int dc[] = {0, 1, 0, -1};
int visited[301][301];
 
queue<P> q;
 
void dfs(int i, int j, int &ans)
{
    visited[i][j] = ans;
    
    for(int k=0; k<4; k++) {
        int ni = i+dr[k];
        int nj = j+dc[k];
        if(g[ni][nj] && visited[ni][nj]!=ans)
            dfs(ni, nj, ans);
    }
}
 
int solve(int sum)
{
    int ans=0;
    while(sum) {
        ans++;
        queue<M> mq;
        while(!q.empty()) {
            int curR = q.front().r;
            int curC = q.front().c; q.pop();
 
            int cnt = 0;
            for(int k=0; k<4; k++) {
                int nr = curR + dr[k];
                int nc = curC + dc[k];
                if(!g[nr][nc]) cnt++;
            }
            mq.push((M){curR, curC, cnt});    
        }
 
        while(!mq.empty()) {
            int curR = mq.front().r;
            int curC = mq.front().c;
            int cnt = mq.front().cnt; mq.pop();
 
            if(g[curR][curC] > cnt) {
                q.push((P){curR, curC});
                g[curR][curC] -= cnt;
                sum -= cnt;
            }
            else {
                sum -= g[curR][curC];
                g[curR][curC] = 0;
            }
        }
 
        int cnt=0;
        for(int i=0; i<r; i++) {
            for(int j=0; j<c; j++) {
                if(g[i][j] && visited[i][j]!=ans) {
                    cnt++;
                    dfs(i, j, ans);
                    if(cnt == 2) return ans;
                }
            }
        }
    } 
    return 0;
}
 
int main()
{
    scanf("%d%d", &r, &c);
 
    int sum = 0;
    for(int i=0; i<r; i++) {
        for(int j=0; j<c; j++) {
            scanf("%d", &g[i][j]);
            if(g[i][j]) q.push((P){i, j});
            sum += g[i][j];
        }
    }
 
    printf("%d\n", solve(sum));
}

>> 1년전엔 그렇게나 틀렸는데, 이번엔 바로 풀었다. (한번 틀렸는데, 문제 이해를 잘못해서...)

>> 빙산을 일단 q에 담고, 주변에 바다가 얼마나 둘러싸여있는지 mq 에 담은 다음, 녹인다. 그리고 섬이 분리가 되었는지 확인한다.

[4179] 불! : http://boj.kr/4179