글 읽기 - c언어 dfs

byunsanghoon1025 1년 전 0

제가 dfs로 이 문제를 풀었는데 계속 틀린답이 나오네요 ㅠ

어디가 틀린걸까요?

#include <stdio.h>
char N[300][300];
int check[300][300];
int sheep[100000], wolf[100000];
int cnt=0;
void dfs(int i, int j) {
    
    if (N[i][j] == 'v'&&check[i][j]==0) {
        wolf[cnt]++;
    }
    if (N[i][j] == 'o' && check[i][j] == 0) {
        sheep[cnt]++;
    }
    check[i][j] = 1;
    if (N[i][j + 1] == '.' && check[i][j+1] == 0) {
        dfs(i, j + 1);
    }
    if (N[i][j + 1] == 'o' && check[i][j+1] == 0) {
        sheep[cnt]++;
        dfs(i, j + 1);
    }
    if (N[i][j + 1] == 'v' && check[i][j+1] == 0) {
        wolf[cnt]++;
        dfs(i, j + 1);
    }


    if (N[i][j - 1] == '.' && check[i][j-1] == 0) {
        dfs(i, j - 1);
    }
    if (N[i][j - 1] == 'o' && check[i][j-1] == 0) {
        sheep[cnt]++;
        dfs(i, j - 1);
    }
    if (N[i][j - 1] == 'v' && check[i][j-1] == 0) {
        wolf[cnt]++;
        dfs(i, j - 1);
    }


    if (N[i+1][j] == '.' && check[i+1][j] == 0) {
        dfs(i+1,j);
    }
    if (N[i+1][j] == 'o' && check[i+1][j] == 0) {
        sheep[cnt]++;
        dfs(i+1, j );
    }
    if (N[i+1][j] == 'v' && check[i+1][j] == 0) {
        wolf[cnt]++;
        dfs(i+1, j);
    }


    if (N[i-1][j] == '.' && check[i-1][j] == 0) {
        dfs(i-1, j);
    }
    if (N[i-1][j] == 'o' && check[i-1][j] == 0) {
        sheep[cnt]++;
        dfs(i-1, j);
    }
    if (N[i-1][j] == 'v' && check[i-1][j] == 0) {
        wolf[cnt]++;
        dfs(i-1, j);
    }
}

int main() {
    int a, b;
    scanf("%d %d", &a,&b);
    for (int i = 0;i < a;i++) {
        scanf("%s", N[i]);
    }
    for (int i = 0;i < a;i++) {
        for (int j = 0;j < b;j++) {
            if (N[i][j] != '#'&&check[i][j]==0) {
                dfs(i, j);
                
                cnt++;
            }
        }
    }
    for (int i = 0;i < cnt;i++) {
        if (sheep[i] > wolf[i]) {
            wolf[i] = 0;
        }
        else {
            sheep[i] = 0;
        }
   }
    int sumsheep = 0, sumwolf = 0;
    for (int i = 0;i < cnt;i++) {
        sumsheep += sheep[i];
        sumwolf += wolf[i];
    }
    printf("%d %d", sumsheep, sumwolf);
}

flyjb 1년 전 0

dfs에서 다음칸으로 넘어갈 때, 주어진 범위 안에서만 움직이도록 설정해야 합니다. ( 0 <= i < R , 0 <= j < C )

예를 들어서 i=1, j=0 일때에는 j-1 = -1 이므로, 28~38 줄은 진행하지 않아야 합니다.

그리고,

3 4
####
#.o#
####

가 입력으로 주어졌을 때,

dfs(1, 1)이 실행되고,

19번째 줄에서 sheep[0]++ 되고,

20번째 줄에서 dfs(1, 2)가 실행되는데,

dfs(1, 2) 안에서 12번째 줄에서 sheep[0]++가 한번 더 일어나서,

중복으로 체크가 됩니다.

byunsanghoon1025 1년 전 0

이렇게 바꾸니까잘되네요.감사합니다

#include <stdio.h>
char N[300][300];
int check[300][300];
int sheep[100000], wolf[100000];
int cnt = 0;
void dfs(int i, int j) {

    if (N[i][j] == 'v' && check[i][j] == 0) {
        wolf[cnt]++;
    }
    if (N[i][j] == 'o' && check[i][j] == 0) {
        sheep[cnt]++;
    }
    check[i][j] = 1;
    if (N[i][j + 1] == '.' && check[i][j + 1] == 0) {
        check[i][j + 1] = 1;
        dfs(i, j + 1);
    }
    if (N[i][j + 1] == 'o' && check[i][j + 1] == 0) {
        sheep[cnt]++;
        check[i][j + 1] = 1;
        dfs(i, j + 1);

    }
    if (N[i][j + 1] == 'v' && check[i][j + 1] == 0) {
        wolf[cnt]++;
        check[i][j + 1] = 1;
        dfs(i, j + 1);
    }


    if (N[i][j - 1] == '.' && check[i][j - 1] == 0) {
        check[i][j - 1] = 1;
        dfs(i, j - 1);
    }
    if (N[i][j - 1] == 'o' && check[i][j - 1] == 0) {
        check[i][j - 1] = 1;
        sheep[cnt]++;
        dfs(i, j - 1);
    }
    if (N[i][j - 1] == 'v' && check[i][j - 1] == 0) {
        check[i][j - 1] = 1;
        wolf[cnt]++;
        dfs(i, j - 1);
    }


    if (N[i + 1][j] == '.' && check[i + 1][j] == 0) {
        check[i+1][j] = 1;
        dfs(i + 1, j);
    }
    if (N[i + 1][j] == 'o' && check[i + 1][j] == 0) {
        check[i + 1][j] = 1;
        sheep[cnt]++;
        dfs(i + 1, j);
    }
    if (N[i + 1][j] == 'v' && check[i + 1][j] == 0) {
        check[i + 1][j] = 1;
        wolf[cnt]++;
        dfs(i + 1, j);
    }


    if (N[i - 1][j] == '.' && check[i - 1][j] == 0) {
        check[i - 1][j] = 1;
        dfs(i - 1, j);
    }
    if (N[i - 1][j] == 'o' && check[i - 1][j] == 0) {
        check[i - 1][j] = 1;
        sheep[cnt]++;
        dfs(i - 1, j);
    }
    if (N[i - 1][j] == 'v' && check[i - 1][j] == 0) {
        check[i - 1][j] = 1;
        wolf[cnt]++;
        dfs(i - 1, j);
    }
}

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    for (int i = 0;i < a;i++) {
        scanf("%s", N[i]);
    }
    for (int i = 0;i < a;i++) {
        for (int j = 0;j < b;j++) {
            if (N[i][j] != '#' && check[i][j] == 0) {
                dfs(i, j);

                cnt++;
            }
        }
    }
    for (int i = 0;i < cnt;i++) {
        if (sheep[i] > wolf[i]) {
            wolf[i] = 0;
        }
        else {
            sheep[i] = 0;
        }
    }
    int sumsheep = 0, sumwolf = 0;
    for (int i = 0;i < cnt;i++) {
        sumsheep += sheep[i];
        sumwolf += wolf[i];
    }
    printf("%d %d", sumsheep, sumwolf);
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c언어 dfs

byunsanghoon1025 1년 전 0

flyjb 1년 전 0

byunsanghoon1025 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말