글 읽기 - [C++]2206번 문제 시간초과 해결을 어떻게해야할까요...

mycool0905 5년 전 0

DFS 백트래킹 이용해서 풀었는데, 여러 예제 넣어서 다 맞는데... 시간초과를 어떻게 할 수 없네요..

1시간동안 코드 계속 고쳐서 제출해도 똑같네요..

코드의 어떤 부분을 고쳐야 시간초과가 해결될까요?

#include <iostream>
#include <limits>
#include <algorithm>

#define WHITE 0
#define GRAY 1
#define BLACK 2
#define WALL 3

using namespace std;

const int dx[4] = { 0,1,0,-1 };
const int dy[4] = { 1,0,-1,0 };


int field[1000][1000] = { 0, };
int color[1000][1000];
int DFS_count[1000][1000];
int M, N;
int MIN_count = numeric_limits<int>::max();
int flag = 1;

bool isIn(int x, int y)
{
	if (0 <= x && x < M && 0 <= y && y < N)
		return true;
	else
		return false;
}

void DFS(int x, int y)
{
	int newX, newY;

	if (x == M - 1 && y == N - 1)
	{
		MIN_count = min(DFS_count[x][y], MIN_count);
		return;
	}

	for (int i = 0; i < 4; i++)
	{
		newX = x + dx[i];
		newY = y + dy[i];

		if (isIn(newX, newY))
			if (color[newX][newY] == WHITE)
			{
				color[newX][newY] = GRAY;
				DFS_count[newX][newY] = DFS_count[x][y] + 1;
				if (DFS_count[newX][newY] > MIN_count)
					return;

				DFS(newX, newY);
				
				color[newX][newY] = WHITE;
			}
			else if (color[newX][newY] == WALL && flag == 1)
			{
				color[newX][newY] = GRAY;
				DFS_count[newX][newY] = DFS_count[x][y] + 1;
				flag = -1;
				if (DFS_count[newX][newY] > MIN_count)
					return;
				
				DFS(newX, newY);
				
				flag = 1;
				color[newX][newY] = WALL;
			}
	}


	color[x][y] = BLACK;
}

void DFS_visit()
{
	int newX, newY;
	int flag = 1;

	for (int m = 0; m < M; m++)
		for (int n = 0; n < N; n++)
		{
			if (field[m][n] == 0)
				color[m][n] = WHITE;
			else
				color[m][n] = WALL;
			DFS_count[m][n] = 0;
		}
	DFS_count[M - 1][N - 1] = -1;
	DFS_count[0][0] = 1;
	color[0][0] = GRAY;

	DFS(0, 0);
}

int main()
{
	char temp[1001] = { '\0', };

	cin >> M >> N;

	for (int m = 0; m < M; m++)
	{
		cin >> temp;
		for (int n = 0; n < N; n++)
			if (temp[n] == '1')
				field[m][n] = WALL;
			else if (temp[n] == '0')
				field[m][n] = WHITE;
	}

	DFS_visit();

	if (MIN_count == numeric_limits<int>::max())
		cout << -1 << endl;
	else
		cout << MIN_count << endl;

	return 0;
}

chogahui05 5년 전 0

DFS로 어떻게 최단 거리를 계산하나요?

wandbox에서도 Killed 납니다.

11 11
01110000000
01111111111
01110000011
01110000011
01110000011
00000000110
00000000110
00000000110
00000000110
00000000110
00000000110

mycool0905 5년 전 0

@chogahui05

일단 지나온 블록의 수를 DFS_count라는 2차원배열에 저장을해놓구요

if (x == M - 1 && y == N - 1) { MIN_count = min(DFS_count[x][y], MIN_count); return; }

이 코드로 최소값을 정하고 있습니다.

혹시 DFS로 푸는게 안되는 문제인가요?

chogahui05 5년 전 1

저 데이터를 돌리시는 환경에 넣어보세요.

저 데이터는 INPUT 최대 크기의 단 121/10000일 뿐입니다.

djm03178 5년 전 1

혼자서 힘들어하시지 말고, 질문을 올릴 때 위에 읽으라고 나오는 공지사항에서 굵은 글씨로 쓰여 있는 문장처럼 질문 게시판을 보세요. https://www.acmicpc.net/board/... 이렇게 좋은 글이 있습니다.

chogahui05 5년 전 1

아직 BFS와 DFS에 대해서 헷갈려 하시는 거 같네요.

여기서 더 답변드리면 의미 없을 거 같고요.

(1) BFS와 DFS가 작동하는 방식 제대로 이해하고 오세요.

(2) 제가 드린 데이터 말고 MYCOOL님이 직접 자신이 작성한 저 코드에서 시간초과가 나는 데이터를 직접 만들어 보세요.

그게 선행되지 않으면 나중에 비슷한 문제를 풀 때 똑같이 접근하실 겁니다.

mycool0905 5년 전 0

@chogahui05

@djm03178

네 아직 많이 부족하네요

조언 감사합니다!

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

문제

문제

출처

ICPC

[C++]2206번 문제 시간초과 해결을 어떻게해야할까요...

mycool0905 5년 전 0

chogahui05 5년 전 0

mycool0905 5년 전 0

chogahui05 5년 전 1

djm03178 5년 전 1

chogahui05 5년 전 1

mycool0905 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말