Week 1 - DFS

< 180219 >

Week 1 - DFS 

[BOJ/2667] 단지번호 붙이기 (http://boj.kr/2667)

1)

#include <cstdio>
#include <algorithm>
 
#define N 101
int n, cnt, a[N][N], s[N];
 
bool safe(int x, int y)
{
    return (0 <= x && x < n) && (0<= y && y < n);
}
 
bool cmp(int a, int b)
{
    return a < b;
}
 
void dfs(int x, int y, int k)
{
    int i, dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
    a[x][y] = k;
    for(i=0; i<4; i++)
        if(safe(x+dx[i], y+dy[i]) && a[x+dx[i]][y+dy[i]]==1 )
            dfs(x+dx[i], y+dy[i], k);
}    
 
void solve(void)
{
    int i, j;
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            if(a[i][j] == 1)
            {
                cnt++;
                dfs(i, j, cnt+1);
            }
 
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            if(a[i][j])
                s[a[i][j]-2]++;
 
    std::sort(s, s+cnt, cmp);
}
 
int main(void)
{
    int i, j;
    scanf("%d", &n);
 
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            scanf("%1d", &a[i][j]);
 
    solve();
 
    printf("%d\n", cnt);
    for(i=0; i<cnt; i++)
        printf("%d\n", s[i]);
 
    return 0;
}

2) 이런식으로도 구현할 수 있다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, cnt, a[101][101];
vector<int> v;
 
bool safe(int x, int y)
{
    return (0 <= x && x < n) && (0<= y && y < n);
}
 
int dfs(int x, int y)
{
    int i, dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
    int ret = 1;
    a[x][y] = 0;
    for(i=0; i<4; i++)
        if(safe(x+dx[i], y+dy[i]) && a[x+dx[i]][y+dy[i]]==1 )
            ret += dfs(x+dx[i], y+dy[i]);
    return ret;
}    
 
void solve(void)
{
    int i, j;
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) {
            if(a[i][j] == 1)
            {
                cnt++;
                v.push_back(dfs(i, j));
            }
        }
    }
 
    sort(v.begin(), v.end());
}
 
int main(void)
{
    int i, j;
    scanf("%d", &n);
 
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            scanf("%1d", &a[i][j]);
 
    solve();
 
    printf("%d\n", cnt);
    for(i=0; i<cnt; i++)
        printf("%d\n", v[i]);
 
}
 

>> dfs() 의 리턴형이 int 이다. 결국 dfs() 호출된 횟수를 리턴하게 된다.

>> vector 를 사용했다.

[BOJ/1012] 유기농 배추 (http://boj.kr/1012)

#include <stdio.h>
 
int r, c;
int g[51][51];
int dr[]={1, 0, -1, 0};
int dc[]={0, 1, 0, -1};
 
int safe(int i, int j)
{
    return (0 <= i && i < r) && (0 <= j && j < c);
}
 
void dfs(int r, int c)
{
    int k;
    g[r][c] = 0;
 
    for(k=0; k<4; k++) {
        int nr = r + dr[k];
        int nc = c + dc[k];
        if(safe(nr, nc) && g[nr][nc])
            dfs(nr, nc);
    }
 
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
    
    while(tc--) {
        int i, j, k;
        int ans = 0;
        scanf("%d%d%d", &r, &c, &k);
    
        while(k--) {
            int a, b;
            scanf("%d%d", &a, &b);
            g[a][b] = 1;
        }
                
        for(i=0; i<r; i++) {
            for(j=0; j<c; j++) {
                if(g[i][j]) {
                    ans++;
                    dfs(i, j);
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

>> 16 : 방문체크 배열을 따로 안만들고, 방문한곳을 0으로 바꿔줌으로써 다시 방문할 수 없도록 하였다.

[BOJ/4963] 섬의 개수 (http://boj.kr/2963)

#include <stdio.h>
 
int r, c;
int g[51][51];
int di[]={-1, -1, -1, 0, 0, 1, 1, 1};
int dj[]={-1, 0, 1, -1, 1, -1, 0, 1};
 
int safe(int i, int j)
{
    return (0 <= i && i < r) && (0 <= j && j < c);
}
 
void dfs(int i, int j)
{
    int k;
    g[i][j] = 0;
 
    for(k=0; k<8; k++) {
        int ni = i+di[k];
        int nj = j+dj[k];
        if(safe(ni, nj) && g[ni][nj])
            dfs(ni, nj);
    }
}
 
int main()
{
    while(1) {
        int i, j;
        int ans=0;
        scanf("%d%d", &c, &r);
 
        if(!r && !c) break;
        
        for(i=0; i<r; i++)
            for(j=0; j<c; j++)
                scanf("%d", &g[i][j]);
 
        for(i=0; i<r; i++) {
            for(j=0; j<c; j++) {
                if(g[i][j]) {
                    ans++;
                    dfs(i, j);
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

>> 위와 같은 유형의 문제. 차이점이라면 8방탐색..!!