글 읽기 - 시간초과 질문드립니다.

rudghks112345 1년 전 0

재귀함수 없이 스택을 이용해서 DFS구현해서 문제를 풀어봤는데, 70%정도에서 시간초과가 뜹니다..

(여러가지 반례들은 다 입력 해봤는데, 결과 값은 정확하게 나오는 것 같습니다.)

스택 이용해서 풀 수 있는 방법이 없을까요 ??

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#pragma warning(disable: 4996)
#define MAX_SIZE 21

int max_count = 0;
int alpha_count = 0;
char graph[MAX_SIZE][MAX_SIZE] = { 0, };
int re[3] = { 0, };
int visited[26] = { 0, };
int Vector_x[4] = { 1, -1, 0, 0 };
int Vector_y[4] = { 0, 0, 1, -1 };

typedef struct Node
{
    int x, y, len;
    int visit[26];
    struct Node* next;
}Node;

typedef struct Stack
{
    Node* top;
}Stack;

void InitStack(Stack* stack);
int IsEmpty(Stack* stack);
void Push(Stack* stack, int x, int y, int len);
void Pop(Stack* stack);
void DFS_count(int x, int y, int R, int C);

int main(void) {
    int R, C;
    char* alpha = (char*)malloc(sizeof(char) * 26);
    for (int i = 0; i < 26; i++)
        alpha[i] = 0;

    scanf("%d %d", &R, &C);

    for (int i = 0; i < R; i++) {
        scanf("%s", graph[i]);
    }
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (alpha[graph[i][j] - 65] == 0) {
                alpha_count++;
                alpha[graph[i][j] - 65] = 1;
            }
        }
    }
    

    DFS_count(0, 0, R, C);
    printf("%d", max_count);

}


void InitStack(Stack* stack)
{
    stack->top = NULL;
}

int IsEmpty(Stack* stack)
{
    return stack->top == NULL;
}

void Push(Stack* stack, int x, int y, int len)
{
    Node* now = (Node*)malloc(sizeof(Node));
    now->x = x;
    now->y = y;
    now->len = len;
    for (int i = 0; i < 26; i++) {
        now->visit[i] = visited[i];
    }
    now->next = stack->top;
    stack->top = now;
}

void Pop(Stack* stack)
{
    Node* now;
    if (IsEmpty(stack))
    {
        return 0;
    }
    now = stack->top;
    re[0] = now->x;
    re[1] = now->y;
    re[2] = now->len;
    for (int i = 0; i < 26; i++) {
        visited[i] = now->visit[i];
    }

    stack->top = now->next;
    free(now);
}

void DFS_count(int x, int y, int R, int C) {
    Stack stack;
    InitStack(&stack);
    Push(&stack, x, y, 1);

    while (!IsEmpty(&stack)) {
        Pop(&stack);

        visited[graph[re[1]][re[0]] - 65] = 1;

        for (int i = 0; i < 4; i++) {
            int cal_x = re[0] + Vector_x[i];
            int cal_y = re[1] + Vector_y[i];
            if (cal_x < 0 || cal_y < 0 || cal_x >= C || cal_y == R)
                continue;
            if (visited[graph[cal_y][cal_x] - 65] == 0) {
                Push(&stack, cal_x, cal_y, re[2] + 1);
            }
        }
        if (max_count < re[2])
            max_count = re[2];
        if (max_count == alpha_count)
            break;
    }
}

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

문제

문제

출처

ICPC

시간초과 질문드립니다.

rudghks112345 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말