글 읽기 - 질문있습니다!!(게시판읽었어요)

porrshe 5년 전 0

음 일단 ㅜㅜdfs를 처음들어가게됬어요.

미로탐색문제를 dfs로 푸는데 70%까지 올라가더니 틀렸습니다 나오더라구요,,

그후로 미로탐색필독게시판읽었습니당.

그래도 궁금해요 제소스틀린부분을 고쳐도 마지막엔 시간초과가 뜰까요?

제 소스가 dfs방식이 맞는지 궁금합니다.또 혹시 여기서 고칠 수 있다면 어떻게 고쳐야 할지 알 수 있을까요?

최저값을뽑기위해 check배열방에 987을 넣음
dfs돌림 ->가려는 길이 '1'이면 상하좌우로 뻗어나감
최소값을 뽑기위해 check[y][x]>cnt일때만 들어감

#include <stdio.h>
using namespace std;
int n, m;
int check[104][104] = { 0, };
char input[104][104] = { 0, };
int dx[4] = { 0,1,-1,0 };
int dy[4] = { 1,0,0,-1 };
void dfs(int y, int x, int cnt)
{
	if (y == n - 1 && x == m - 1)
	{
		if (check[y][x] > cnt)check[y][x] = cnt;
		return;
	}
	if (check[y][x]>cnt)
	{
		check[y][x] = cnt;
		for (int i = 0; i < 4; i++)
		{
			if (0 <= x + dx[i] < m && 0 <= y + dy[i] < n)
			{
				if (input[y + dy[i]][x + dx[i]] == '1')dfs(y + dy[i], x + dx[i], cnt + 1);
			}
		}
	}
}

int main(void)
{
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++)scanf("%s",input[i]);

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)check[i][j] = 987;

	dfs(0, 0,1);
	printf("%d", check[n-1][m-1]);
	return 0;
}

jh05013 5년 전 0

70%나 올라간다는 것도 신기하군요. 정답이 최대 얼마까지 갈 수 있는지 생각해 보세요.

그리고 FAQ 글을 읽으셨다면 알겠지만, 최단거리 문제는 절대로 DFS로 풀면 안 됩니다. check[y][x]>cnt일 때만 DFS를 진행하면 적어도 이 문제는 풀 수 있지만, BFS보다 훨씬 비효율적이고 입력의 크기가 조금이라도 더 커지면 시간 초과가 납니다.

porrshe 5년 전 1

앗 감사합니다!!

제가 알고리즘시간복잡도를 계산하려고 인터넷검색도해보고 하는데 실제문제에 적용시키려고 하면 감이안잡혀요ㅜㅜ

다양한 알고리즘을 공부하는게 답일까요? 그 시간복잡도를 좌우하는 기준을 잘 못잡겠어요(for문이나 진짜 간단한거 빼고!)예를 들면 dfs나 bfs..?

이걸로 뭘 하느냐에 따라서 시간이 달라지는 건 알겠는 데 어렵네요ㅜㅜ

혹시 시간나시면 조언해주실 수 있을까요..!

porrshe 5년 전 0

일단 제가 틀린부분을 찾아서 수정해서 성공은 시켰습니다!

jh05013 5년 전 2

사용된 알고리즘의 시간복잡도를 알고 있으면 그 복잡도 식에서 사용된 변수의 값을 대입해서 알 수 있습니다. 예를 들어 BFS같은 경우 한 번 방문한 정점을 다시 방문하지 않기 때문에, 정점과 간선의 개수로 시간 복잡도를 결정할 수 있습니다. 그 개수가 얼마인지 문제에서 알아내는 것은 물론 푸는 사람의 몫입니다.

porrshe 5년 전 0

wow 명확해졌어요! 두 분 정말 감사합니다!!

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

문제

문제

출처

ICPC

질문있습니다!!(게시판읽었어요)

porrshe 5년 전 0

jh05013 5년 전 0

porrshe 5년 전 1

porrshe 5년 전 0

jh05013 5년 전 2

porrshe 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말