Week 2 - DFS

<180226>

Week 2 : DFS

[11724] 연결요소의 개수 (http://boj.kr/11724)

1)

#include <stdio.h>
 
int n, m;
int g[1001][1001];
int visited[1001];
 
void dfs(int s)
{
    int i;
    visited[s] = 1;
 
    for(i=1; i<=n; i++) {
        if(g[s][i] && !visited[i])
            dfs(i);
    }
 
}
 
int main()
{
    int i, ans=0;
    scanf("%d%d", &n, &m);
 
    while(m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        g[a][b] = g[b][a] = 1;
    }
 
    for(i=1; i<=n; i++) {
        if(!visited[i]) {
            ans++;
            dfs(i);
        }
    }
    printf("%d\n", ans);
    return 0;
}
 

>> DFS 기본 

>> 모든 정점에 대해서 DFS() 실행한 횟수가 컴퍼넌트의 갯수가 된다.

2) 연결리스트를 이용한 구현

#include <stdio.h>
#include <stdlib.h>
 
typedef struct node {
    int v;
    struct node *next;
} Node;
 
typedef struct list {
    Node *head;
} List;
 
void init(List *list)
{
    list->head = NULL;
}
 
void addNode(List *list, int v)
{
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->v = v;
    newNode->next = list->head;
    list->head = newNode;
}
 
int n, m;
List g[1001];
int visited[1001];
 
void dfs(int s)
{
    Node *cur = g[s].head;
    visited[s] = 1;
 
    while(cur != NULL) {
        int next = cur->v;
        if(!visited[next]) dfs(next);
        else cur = cur->next;
    }
}
 
int main()
{
    int i, ans=0;
    scanf("%d%d", &n, &m);
 
    for(i=0; i<=n; i++)
        init(g+i);
 
    while(m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        addNode(g+a, b);
        addNode(g+b, a);
    }
      
    for(i=1; i<=n; i++) {
        if(!visited[i]) {
            ans++;
            dfs(i);
        }
    }
    printf("%d\n", ans);
    return 0;
}
 

[10026] 적록색약 

#include <stdio.h>
 
int n;
char g[101][101];
int visited[101][101];
int di[]={1, 0, -1, 0};
int dj[]={0, 1, 0, -1};
 
int safe(int i, int j)
{
    return (0 <= i && i < n) && (0 <= j && j < n);
}
 
void dfs(int i, int j, char color)
{
    int k;
    visited[i][j] = 1;
    for(k=0; k<4; k++) {
        int ni = i+di[k];
        int nj = j+dj[k];
        if(safe(ni, nj) && !visited[ni][nj] && g[ni][nj] == color)
            dfs(ni, nj, color);
    }
}
 
void go()
{
    int i, j, ans=0;
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) {
           if(!visited[i][j]) {
                ans++;
                dfs(i, j, g[i][j]);
           }
        }
    }
    printf("%d\n", ans);
}
 
int main()
{
    int i, j;
    int rb=0, rgb=0;
    scanf("%d", &n);
 
    for(i=0; i<n; i++)
        scanf("%s", g[i]);
 
    go();
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) {
            visited[i][j] = 0;
            if(g[i][j] == 'G')
                g[i][j] = 'R';
        }
    }
    
    go();
    return 0;
}
 

>> 

[2606] 바이러스

#include <stdio.h>
 
int n, m;
int g[101][101];
int visited[101];
 
int dfs(int s)
{
    int i, ret=1;
    visited[s] = 1;
    for(i=1; i<=n; i++) {
        if(g[s][i] && !visited[i])
            ret += dfs(i);
    }
    return ret;
}
 
int main()
{
    scanf("%d%d", &n, &m);
   
    while(m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        g[a][b] = g[b][a] = 1;
    }
        
    printf("%d\n", dfs(1)-1);
 
    return 0;
}

>> 1번 컴퓨터에서 갈 수 있는 컴퓨터의 갯수.

[2583] 영역구하기

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int m, n, k;
int g[105][105];
int dr[]={1, 0, -1, 0};
int dc[]={0, 1, 0, -1};
 
bool safe(int r, int c)
{
    return (0 <= r && r < m) && (0 <= c && c < n); 
}
 
int dfs(int r, int c)
{
    int ret=1;
    g[r][c] = 1;
    for(int k=0; k<4; k++) {
        int nr = r+dr[k];
        int nc = c+dc[k];
        if(safe(nr, nc) && !g[nr][nc])
            ret += dfs(nr, nc);
    }
    return ret;
}
 
int main()
{
    int r, c, ans=0;
    scanf("%d%d%d", &m, &n, &k);
 
    while(k--) {
        int x, y, x2, y2;
        scanf("%d%d%d%d", &x, &y, &x2, &y2);
 
        for(r=y; r<y2; r++)
            for(c=x; c<x2; c++)
                g[r][c] = 1;
    } 
 
 
    vector<int> v;
    for(r=0; r<m; r++) {
        for(c=0; c<n; c++) {
            if(!g[r][c]) {
                ans++;
                v.push_back(dfs(r, c));
            }
        }
    }
    sort(v.begin(), v.end());
    printf("%d\n", ans);
    for(int i=0; i<v.size(); i++)
        printf("%d ", v[i]);
    puts("");
}

>> 영역을 칠하는 것이 핵심인데, 이게 좀 헷갈린다.

>> 영역만 구하면 다음에 할일은 컴퍼넌트 갯수 구하기와 동일하다.

[10451] 순열 사이클

#include <stdio.h>
 
int n;
int g[1001][1001];
int visited[1001];
 
void dfs(int s)
{
    int i;
    visited[s] = 1;
 
    for(i=1; i<=n; i++) {
        if(g[s][i] && !visited[i])
            dfs(i);
    }
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int i, j, k;
        int ans=0;
        scanf("%d", &n);
 
        for(i=1; i<=n; i++) {
            scanf("%d", &k);
            g[i][k] = 1;
        }
 
        for(i=1; i<=n; i++) {
            if(!visited[i]) {
                ans++;
                dfs(i);
            }
        }
        
        printf("%d\n", ans);
 
        for(i=1; i<=n; i++) {
            visited[i] = 0;
            for(j=1; j<=n; j++)
                g[i][j] = 0;
        }
    }
    return 0;
}

>> 그래프 모델링 후 컴퍼넌트 구하는 문제.

[]