Week3 - DFS

<180310>

Week3 - DFS

[1743] 음식물 피하기 (http://boj.kr/1732)

#include <stdio.h>
 
int n, m;
int g[101][101];
int dr[]={1, 0, -1, 0};
int dc[]={0, 1, 0, -1};
 
int safe(int a, int b)
{
    return (0 < a && a <= n) && (0 < b && b <= m);
}
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int dfs(int r, int c)
{
    int k, ret=1;
    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])
            ret += dfs(nr, nc);
    }
    return ret;
}
 
int main()
{
    int i, j, k;
    int ans=0;
    scanf("%d%d%d", &n, &m, &k);
    
    while(k--) {
        int a, b;
        scanf("%d%d", &a, &b);
        g[a][b] = 1;
    }
 
    for(i=1; i<=n; i++) {
        for(j=1; j<=m; j++) {
            if(g[i][j]) {
                ans = max(ans, dfs(i, j));
            }
        }
    }
 
    printf("%d\n", ans);
    return 0;
}
 

[2468] 안전영역 (http://boj.kr/2468)

1)

#include <stdio.h>
 
int n;
int g[101][101];
int visited[101][101];
int di[]={0, 1, 0, -1};
int dj[]={1, 0, -1, 0};
 
int safe(int i, int j)
{
    return (0 <= i && i < n) && (0 <= j && j < n);
}
 
void dfs(int i, int j, int k)
{
    visited[i][j] = k;
 
    for(int a=0; a<4; a++) {
        int ni = i+di[a];
        int nj = j+dj[a];
        if(safe(ni, nj) && g[ni][nj] >= k && visited[ni][nj] != k) 
            dfs(ni, nj, k);
    }
}
 
int main()
{
    int i, j, k;
    int max=1, min=100;
    int ans=0;
    scanf("%d", &n);
 
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) {
            scanf("%d", &k);
            if(max < k) max = k;
            if(min > k) min = k;
            g[i][j] = k;
        }
    }
 
    for(k=min; k<=max; k++) {
        int tmp=0;
        for(i=0; i<n; i++) {
            for(j=0; j<n; j++) {
                if(g[i][j] >= k && visited[i][j] != k) {
                    tmp++;
                    dfs(i, j, k);
                }
            }
        }
        if(ans < tmp) ans = tmp; 
    }
    printf("%d\n", ans);
    return 0;
}

>> 42 라인에서 k<max 로 해서 한번 틀렸음.

이렇게 할 경우 

2

1 1

1 1

의 테케의 정답은 1인데 0이나옴.

2) 1년 전 풀이

#include <stdio.h>
 
int n, ans, g[100][100], ck[100][100];
 
int safe(int x, int y)
{
    return (0 <= x && x < n) && (0 <= y && y < n); 
}
 
void dfs(int y, int x, int k)
{
    int i, xx, yy, dx[]={1, 0, -1, 0}, dy[]={0, 1, 0, -1};
    ck[y][x] = 1;
 
    for(i=0; i<4; i++) {
        xx = x+dx[i];
        yy = y+dy[i];
        if(safe(xx, yy) && g[yy][xx] > k && !ck[yy][xx])
            dfs(yy, xx, k);
    }
}
 
int main()
{
    int i, j, k, max=0;
    scanf("%d", &n);
 
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) {
            scanf("%d", &g[i][j]);
            if(g[i][j] > max)
                max = g[i][j];
        }
    }
 
    for(k=0; k<max; k++) {
        int cnt=0;
        for(i=0; i<n; i++) {
            for(j=0; j<n; j++) {
                if(g[i][j] > k && !ck[i][j]) {
                    dfs(i, j, k);
                    cnt++;
                }
            }
        }
        
        if(ans < cnt)
            ans = cnt;
 
        for(i=0; i<n; i++)
            for(j=0; j<n; j++)
                ck[i][j] = 0;
    }
 
    printf("%d\n", ans);
    return 0;
}

>> 거의 비슷하게 푼것 같다.

[11403] 경로찾기 (http://boj.kr/11403)

1) DFS 풀이

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

>> dfs(i, j) : i 에서 j로 가는 길이 있는지 알려주는 함수.

>> 13, 14 : s 에서 i로 가는 길이 있는데, i가 e 라면, s에서 e로 가는 길이 있다는 뜻!!

2) 플로이드 풀이

#include <stdio.h>
 
int g[101][101];
 
int main()
{
    int i, j, k, n;
    scanf("%d", &n);
 
    for(i=0; i<n; i++)  
        for(j=0; j<n; j++) 
            scanf("%d", &g[i][j]);
    
 
    for(k=0; k<n; k++)
        for(i=0; i<n; i++)
            for(j=0; j<n; j++)
                if(g[i][k] && g[k][j])
                    g[i][j] = 1;
    
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++)
            printf("%d ", g[i][j]);
        puts("");
    }
 
    return 0;
}

>> 플로이드 와샬 풀이가 좀더 직관적이긴 하다. 코드도 심플하고.

>> 하지만 DFS 로 풀수 있다고 해서 과제로 내주었다...얘들아 미안..ㅎㅎ

>> 18, 19 : i 에서 k로 가는 길이 있는데, k에서 j로 가는 길이 있으면 i 에서 j로 가는 길이 있다..!!

[9466] 텀 프로젝트

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

>> 예전에 엄청 고통 받았던 문제..

>> 여전히 고통스럽다.

>> 결국 라이님의 블로그 설명을 보고 해결했었다. (https://kks227.blog.me/221028710658)

>> 사이클에 대한 처리를 배열하나를 더 만들어서 해야한다.

>> visited[next] = finished[next] = 0 : 아직 방문하지 않은 정점

>> visited[next] = 1 && finished[next] = 0 : 현재 정점과 next가 하나의 싸이클에 속함.

>> visited[next] = finished[next] = 1 : 이미 모든 탐색이 끝난 정점. 현재 정점은 next 가 그 싸이클 안에 있건 없건 절대 그 싸이클 안에 있을 수 없음.

[1707] 이분 그래프 (http://boj.kr/1707)

#include <cstdio>
#include <vector>
using namespace std;
 
int ans;
 
void isBinaryGraph(vector<int> g[], vector<int> &visited, int s, int ck)
{
    
    visited[s] = ck%2+1;
 
    for(int i=0; i<g[s].size() && ans; i++) {
        int next = g[s][i];
        if(!visited[next]) {
            isBinaryGraph(g, visited, next, ck+1);
        }
        else {
            if(visited[s] == visited[next]) {
                ans = 0;
                return ;
            }
        }
    }
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
    
    while(tc--) {
        int v, e;
        scanf("%d%d", &v, &e);
 
        vector<int> g[20001];
        vector<int> visited(v+1, 0);
 
        while(e--) {
            int a, b;
            scanf("%d%d", &a, &b);
            g[a].push_back(b);
            g[b].push_back(a);
        }
        
        ans = 1;
        for(int i=1; i<=v; i++) {
            if(!visited[i] && ans)
                isBinaryGraph(g, visited, i, 0);
        }
        ans ? puts("YES") : puts("NO");
    }
}

>> 방문체크를 1과 2로 처리하였다. 

>> 다음에 방문할 정점이 이미 방문을 한 정점인데, 같은 번호로 방문체크가 되어 있으면 이분그래프가 아니다.

>> 46 : 컴퍼넌트는 여러개일 수 있다..