글 읽기 - 예제 2와 시간 문제

adfsfsf 5년 전 0

예제 2번처럼 되어 있는 문제를 통과시키려고 한 줄을 추가하면 시간초과가 일어납니다.

해당 줄은 43번 줄입니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long int n, m, min, **visit;
int di[4] = { 1,0, 0, -1 }, dj[4] = { 0,1,-1,0 };
void check(int i, int j, int count, char **nums);
int main(void)
{
	int i;
	char **a;
	scanf("%ld %ld", &n, &m);
	a = (char **)calloc(n, sizeof(char *));
	visit = (int **)calloc(n, sizeof(int *));
	for (i = 0; i < n; i++)
		visit[i] = (int *)calloc(m, sizeof(int));
	for (i = 0; i < n; i++)
	{
		a[i] = (char *)calloc(m + 1, sizeof(char));
		scanf("%s", a[i]);
	}
	min = m * n;
	check(0, 0, 0, a);
	printf("%ld\n", min);
	return 0;
}
void check(int i, int j, int count, char **nums)
{
	int a;
	if (i == n - 1 && j == m - 1)
	{
		if (min > count + 1)
			min = count + 1;
	}
	else
	{
		visit[i][j] = 1;
		for (a = 0; a < 4; a++)
		{
			if (i + di[a] < 0 || j + dj[a] < 0 || i + di[a] >= n || j + dj[a] >= m || nums[i + di[a]][j + dj[a]] != '1'||visit[i+di[a]][j+dj[a]]!=0)
				continue;
			check(i + di[a], j + dj[a], count + 1, nums);
		}
        //visit[i][j] = 0;
	}
}

jh05013 5년 전 0

질문을 올릴 때 "아래 공지사항을 먼저 읽고 글을 작성해 주세요." 라는 말이 나오는데 읽으셨나요? 그 글의 맨 처음에 굵은 글씨로 "질문 검색을 먼저 해서 자신에게 필요한 답변이나 반례가 없는지 확인하고 질문을 남겨주세요." 라는 말이 적혀 있습니다.

adfsfsf 5년 전 0

공지사항은 확인했습니다. 다른 글들을 봤는데, 해결될 만한 글을 못 찾았습니다. 위의 소스에 주석을 달아서 새로 적겠습니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long int n, m, min, **visit;//visit은 방문 여부를 체크하는 배열, min은 최소 경로 값을 저장할 변수
int di[4] = { 1,0, 0, -1 }, dj[4] = { 0,1,-1,0 };//방향 설정
void check(int i, int j, int count, char **nums);
int main(void)
{
	int i;
	char **a;//맵을 저장할 배열
	scanf("%ld %ld", &n, &m);
	a = (char **)calloc(n, sizeof(char *));
	visit = (int **)calloc(n, sizeof(int *));
	for (i = 0; i < n; i++)
		visit[i] = (int *)calloc(m, sizeof(int));
	for (i = 0; i < n; i++)
	{
		a[i] = (char *)calloc(m + 1, sizeof(char));
		scanf("%s", a[i]);
	}
	min = m * n;
	check(0, 0, 0, a);
	printf("%ld\n", min);
	return 0;
}
void check(int i, int j, int count, char **nums)
{
	int a;
	if (i == n - 1 && j == m - 1)
	{
		if (min > count + 1)
			min = count + 1;
	}
	else
	{
		visit[i][j] = 1;//이동 표시
		for (a = 0; a < 4; a++)
		{
			if (i + di[a] < 0 || j + dj[a] < 0 || i + di[a] >= n || j + dj[a] >= m || nums[i + di[a]][j + dj[a]] != '1'||visit[i+di[a]][j+dj[a]]!=0)//이동할 수 있는 칸이 아니면
				continue;
			check(i + di[a], j + dj[a], count + 1, nums);//이동해서 계속
		}
        //visit[i][j] = 0;
	}
}

jh05013 5년 전 1

눈에 띄는 제목을 가진 FAQ 글이 있습니다.

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

거기에 "DFS는 통과될 수 없습니다. DFS는 모든 가능한 경로를 탐색하는데 이는 지수 시간복잡도가 됩니다. 이 문제의 분류에 BFS만 있는 이유가 그것입니다."라고 적혀 있습니다.

43줄을 넣었을 때 시간초과 나는 이유도 이것이고, 43줄을 빼면 제대로 된 답이 안 나옵니다. DFS는 최단거리와 아무 관련이 없습니다.

adfsfsf 5년 전 0

제가 BFS와 DFS의 차이를 잘못 이해했었군요. 감사합니다.

adfsfsf 5년 전 0

그런데, BFS로 쓰니까 DFS로 쓸 때의 2배 정도의 길이가 나오는데도, 3중 루프를 쓰는데도 빨리 끝난다는 점이 신기하네요.

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

문제

문제

출처

ICPC

예제 2와 시간 문제

adfsfsf 5년 전 0

jh05013 5년 전 0

adfsfsf 5년 전 0

jh05013 5년 전 1

adfsfsf 5년 전 0

adfsfsf 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말