글 읽기 - 끙끙

nuricook 7년 전 0

안녕하세요!,,

1012문제는 0, 0부터 N-1, M-1까지 dfs를 돌려서, 떨어져있는 구역을 count하는 문제로 이해했습니다.

제가 입력한 예제는 전부 잘 맞게 나오는데요,

왜 틀렸다고 나오는지 모르겠네요...

혹시 좋은 반례가 있으시면 부탁드립니다!

#include <stdio.h>

#define MAXN 51
int map[MAXN][MAXN];
int N, M, K;

void intput()
{
    scanf("%d %d %d\n", &N, &M, &K);
    int i, j;
    for (i = 0; i < N; i++) {
        for (j = 0; j < M; j++) {
            map[i][j] = 0;
        }
    }
    for (i = 0; i < K; i++) {
        int x, y;
        scanf("%d %d\n", &x, &y);
        map[x][y] = 1;
    }
}

int dfs(int visited[MAXN][MAXN], int x, int y)
{
    if (x < 0 || x >= N || y < 0 || y >= N)
        return 0;
    if (visited[x][y] || map[x][y] == 0)
        return 0;

    visited[x][y] = 1;

    int size = 1;
    size += dfs(visited, x + 1, y);  // D
    size += dfs(visited, x - 1, y);  // U
    size += dfs(visited, x, y + 1);  // R
    size += dfs(visited, x, y - 1);  // L
    return size;
}

int dfsall()
{
    int visited[MAXN][MAXN] = {0, };
    int i, j, totalareacnt = 0;
    for (i = 0; i < N; i++) {
        for (j = 0; j < M; j++) {
            int areasize = dfs(visited, i, j);
            if (areasize) {
                totalareacnt++;
            }
        }
    }
    return totalareacnt;
}

int main()
{
    setbuf(stdout, NULL);

    int T;
    scanf("%d\n", &T);
    while (T--) {
        intput();
        printf("%d\n", dfsall());
    }

    return 0;
}

kipa00 7년 전 2

이 테스트 케이스의 경우 DFS를 재귀로 돌리면 스택 오버플로우가 발생할 거 같아요.

august14 7년 전 2

스택 오버플로우 문제가 아닙니다.

25번째줄 y조건이 잘 못 됐어요

nuricook 7년 전 0

@klpa00님, @august14님,

답변 감사합니다 :)

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

문제

문제

출처

ICPC

끙끙

nuricook 7년 전 0

kipa00 7년 전 2

august14 7년 전 2

nuricook 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말