글 읽기 - 쉬운문제인줄 알았는데, 시간초과 뜨네요

sohnryang 5년 전 0

간단하게 dfs로 코딩했는데 시간초과 뜹니다. 한번 봐주시면 감사하겠습니다.

/*
 * Baekjoon Online Judge #16946
 * https://www.acmicpc.net/problem/16946
 */

#include <bits/stdc++.h>

using namespace std;

int in_n, in_m, in_map[1001][1001], result[1001][1001], visited[1001][1001];
const int dy[] = {-1, 0, 0, 1}, dx[] = {0, -1, 1, 0};

inline bool in_range(int y, int x) {
    return y >= 0 && y < in_n && x >= 0 && x < in_m;
}

int floodfill(int y, int x) {
    if (!in_range(y, x)) return 0;
    if (in_map[y][x]) return 0;
    if (visited[y][x]) return 0;
    visited[y][x] = 1;
    int ret = 1;
    for (int i = 0; i < 4; ++i)
        ret += floodfill(y + dy[i], x + dx[i]);
    return ret;
}

void crack_n_move() {
    for (int y = 0; y < in_n; ++y) {
        for (int x = 0; x < in_m; ++x) {
            if (in_map[y][x]) {
                in_map[y][x] = 0;
                memset(visited, 0, sizeof(visited));
                result[y][x] = floodfill(y, x) % 10;
                in_map[y][x] = 1;
            }
            else result[y][x] = 0;
        }
    }
}

void print() {
    for (int y = 0; y < in_n; ++y) {
        for (int x = 0; x < in_m; ++x)
            printf("%d", result[y][x]);
        printf("\n");
    }
}

int main() {
    memset(in_map, -1, sizeof(in_map));
    memset(result, -1, sizeof(result));
    scanf("%d %d", &in_n, &in_m);
    for (int y = 0; y < in_n; ++y) {
        char input[1001];
        scanf("%s", input);
        for (int x = 0; x < in_m; ++x)
            in_map[y][x] = input[x] - '0';
    }
    crack_n_move();
    print();
    return 0;
}

luniro 5년 전 1

각 1에서부터 dfs로 구현하면 시간초과가 뜹니다

이와 같은 형태로 들어오게 되면 O(M^2 N^2)이 되어 1000 by 1000이 되면 시간초과가 발생합니다

sohnryang 5년 전 0

음.. 그럼 BFS는 괜찮을까요?

luniro 5년 전 0

지금 방식으로는 bfs dfs에 관계없이 시간초과가 발생합니다

sohnryang 5년 전 0

약간만 힌트라도 주시면 안될까요..?

luniro 5년 전 1

저도 같은 방법으로 접근했다가 시간초과를 겪고 수정했습니다 제가 사용한 방법은 1을 따로 0으로 변환하지 않고 각 0 묶음의 갯수를 dfs로 헤아렸습니다 그 후 각 1마다 상하좌우에 0이 있는 경우 각 묶음의 합을 모두 더한 후 +1하는 식으로 계산했습니다

그러니깐 지금의 방식은 0이 넓게 연결되어있으면 dfs나 bfs를 통해 중복해서 카운트를 하게 되는데, 0을 미리 한 번만 세서 각 1을 중심으로 더해서 중복으로 계산하는 것을 줄였습니다

다만 이 방법에서는 처음의 예시와 같이 하나의 1 주변에 한 묶음의 0이 상하좌우에 중복 될 경우 한 번만 더해지도록 구현해야합니다

sohnryang 5년 전 0

네 한번 그렇게 풀어보겠습니다. 답변 감사합니다 ㅎㅎㅎ

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

문제

문제

출처

ICPC

쉬운문제인줄 알았는데, 시간초과 뜨네요

sohnryang 5년 전 0

luniro 5년 전 1

sohnryang 5년 전 0

luniro 5년 전 0

sohnryang 5년 전 0

luniro 5년 전 1

sohnryang 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말