글 읽기 - 7576 시간 초과

s_um 3년 전 0

다른 분들의 글을 봐도 비슷한 방식으로 하시는 것 같던데 제가 잘못 이해한건가요ㅠㅠㅠ

반복해서 읽어봐도 아래 코드 방식밖에 생각이 안나서요ㅠㅠ

#include <stdio.h>
#include <stdlib.h>

typedef struct s_q
{
        int x;
        int y;
        int day;
        struct s_q *next;
}q;

int **makeMap(int rowLen, int colLen);
void freeMap(int **map, int rowLen);

int getMinDay(int **map, int rowLen, int colLen);

void pushQ(q **que, int y, int x, int day);
q *popQ(q **que);

int main(void)
{
        int rowLen, colLen;
        int **map;

        scanf("%d %d",&colLen,&rowLen);

        map = makeMap(rowLen,colLen);
        printf("%d\n",getMinDay(map,rowLen,colLen));
        freeMap(map,rowLen);
}

int **makeMap(int rowLen, int colLen) //입력받기
{
        int i, j;
        int **map;

        map = (int**)malloc(rowLen*sizeof(int*));
        i = 0;
        while(i<rowLen) {
                map[i] = (int*)malloc(colLen*sizeof(int));
                j = 0;
                while(j<colLen)
                        scanf("%d",map[i]+(j++));
                ++i;
        }
        return map;
}

void freeMap(int **map, int rowLen) //동적할당해준 메모리 해제해주기
{
        int i;
        i = 0;
        while(i<rowLen)
                free(map[i++]);
        free(map);
}


int getMinDay(int **map, int rowLen, int colLen)
{
        int day, x, y;
        int i, j;
        q *que;
        q *curLoc;

        i = 0;
        que = NULL;
        while(i<rowLen) { //처음에 주어진 익은토마토를 찾아서 큐에 넣기
                j = 0;
                while(j<colLen) {
                        if(1 == map[i][j]) {
                                pushQ(&que,i,j,0);
                        }
                        ++j;
                }
                ++i;
        }

        curLoc = popQ(&que);
        while(curLoc) { //큐에 아무것도 없어질때까지 반복
                x = curLoc->x;
                y = curLoc->y;
                day = curLoc->day+1;//해당 토마토가 익은 다음날에 익을 토마토므로 +1

                if(y>0 && !map[y-1][x]) { //아랫쪽 토마토가 있으면서 덜익은 토마토일경우
                        map[y-1][x] = 1;
                        pushQ(&que,y-1,x,day);
                }
                if(y<rowLen-1 && !map[y+1][x]) { //위쪽 토마토가 있으면서 덜익은 토마토일경우
                        map[y+1][x] = 1;
                        pushQ(&que,y+1,x,day);
                }
                if(x>0 && !map[y][x-1]) { //왼쪽 토마토가 있으면서 덜익은 토마토일경우
                        map[y][x-1] = 1;
                        pushQ(&que,y,x-1,day);
                }
                if(x<colLen-1 && !map[y][x+1]) { //오른쪽 토마토가 있으면서 덜익은 토마토일경우
                        map[y][x+1] = 1;
                        pushQ(&que,y,x+1,day);
                }

                free(curLoc);
                curLoc = popQ(&que); //본인은 익었으면서 주변 토마토를 익히지않은 토마토 위치정보 가져오기
        }

        i = 0;
        while(i<rowLen) { //만약 덜익은 토마토가 있다면 -1을 반환
                j = 0;
                while(j<colLen) {
                        if(!map[i][j])
                                return -1;
                        ++j;
                }
                ++i;
        }

        return day-1; //마지막 토마토가 익은 다음날을 가르키고있으므로 -1
}


void pushQ(q **que, int y, int x, int day)
{
        q *new;
        q *ptr;
        new = (q*)malloc(sizeof(q));
        new->x = x;
        new->y = y;
        new->day = day;
        new->next = NULL;

        if(*que) {
                ptr = *que;
                while(ptr->next)
                        ptr = ptr->next;
                ptr->next = new;
        }else{
                *que = new;
        }
}

q *popQ(q **que)
{
        q *ret;
        ret = *que;
        if(*que) {
                *que = (*que)->next;
                ret->next = NULL;
        }

        return ret;
}

s_um 3년 전 1

큐에 저장된 값이 많은 경우 푸쉬할때 걸리는 시간으로 인해 시간초과가 떴었습니다.

큐는 연결리스트가 아닌 배열과 두개의 포인터를 이용하여 구현하였을 때 통과가 떴습니다.

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

문제

문제

출처

ICPC

7576 시간 초과

s_um 3년 전 0

s_um 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말