글 읽기 - 시간초과

m48tank1 7년 전 1

Dfs로 문제접근했습니다 . 이문제는 dfs로 풀면 시간초과가 나는건가요?

제가 못하는거겠지만요^^;

Bfs와 dfs를 선택해야하는 기준이 있을까요?

Dfs로 푸신분이 있다면 조언좀 부탁드립니다.

#if 1
#include <stdio.h>
#define INFI 987654321
int N, M;
char DATA[51][51];
int VISIT[64][51][51];
int SX, SY;
int GX, GY;
int MinMove=INFI;

int safe(int x, int y)
{
    if(x>=0 && x<N && y>=0 && y<M) return 1;
    else return 0;
}
int dfs(int x, int y, int key, int cnt)
{
    int dx[4] = { -1, 1, 0, 0};
    int dy[4] = { 0, 0, -1, 1};
    int xx=0, yy=0, kk=0;

    if(MinMove < cnt) return 0;
    if(VISIT[key][x][y] == 1) return 0;

    if(DATA[x][y] == '1')
    {
	//printf("find %d\n", cnt);
        if(MinMove > cnt) MinMove = cnt;
        return 0;
    }
    else if(DATA[x][y]>='A' && DATA[x][y]<='F') //대문이면
    {
        int openkey=0;
        openkey = key & (1 << (DATA[x][y]-'A'));
        if(!openkey) return 0;
    }

    //printf("%d %d %c %d %d \n", x, y, DATA[x][y], key, cnt);
    VISIT[key][x][y] = 1;
    for(int i=0; i<4; i++)
    {
        xx = x + dx[i];
        yy = y + dy[i]; 
        if(safe(xx, yy) && DATA[x][y] !='#') 
        {
			if(DATA[xx][yy]>='a' && DATA[xx][yy]<='f')
			{				
				kk = key | (1 << (DATA[xx][yy]-'a'));
				dfs(xx, yy, kk, cnt+1);
			}
			else
			{
				dfs(xx, yy, key, cnt+1);
			}			
        }
    }

    VISIT[key][x][y] = 0;  //<--- 현재위치에서 상/하/좌/우 길이 없으면 이전으로 돌아가야하므로 0으로 초기화함
	//printf("fin %d %d\n", key, VISIT[key][x][y]);

    return 0;
}

int main()
{
    //freopen("sample_input.txt", "r", stdin);
    //freopen("sample_output.txt", "w", stdout);
    scanf("%d %d", &N, &M);
    for(int i=0; i<N; i++)
    {
        scanf("%s", DATA[i]);
    }

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            if(DATA[i][j]=='0')
            {
                SX = i; SY = j;
            }
        }
    }

    dfs(SX, SY, 0, 0);
    if(MinMove != INFI)printf("%d\n", MinMove);
	else printf("-1\n");
    return 0;
}
#endif

choko100 2년 전 0

안녕하세요, DFS와 BFS 를 간단하게 선택하려면 문제에서 최소 이동 횟수나 최단 거리를 질문하는 것인지 보면 좋을 것 같습니다. DFS는 깊이 우선으로 탐색을 하게 되어서 최단 거리를 찾으려면 거의 모든 점을 다 돌아야될 수도 있지만, BFS는 루트에서부터 가까운 곳들을 탐색해가기 때문에 최단 거리 문제에 적용하기 좋습니다.

본 문제에서는 아래와 같이 이동 횟수의 최솟값을 구하라고 했기 때문에 시간초과를 막기 위해 BFS로 푸는 것이 더 좋을 것 같습니다.

"민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오."

질문 답변 게시판에서 다른 분들이 만들어주신 테스트케이스 중 본 코드의 시간 초과를 확인할 수 있는 예제를 발견하여 공유드립니다.

8 6
abcdef
......
......
.....0
#####.
ABCDEF
.#####
.....1
Answer: 30

https://www.acmicpc.net/board/...

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