글 읽기 - 시간 초과 ... 나네요 뭐가 문제일까요.. 고수님들 ㅠㅠ

ska4773 5년 전 0

시간초과 이유를 잘 모르겠습니다 ㅠㅠ 고수님들 도와주십쇼

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;
int n, m;
char map[500][500];
int visit[500][500];

int res;
queue<pair<int, int>>q;


void bfs() {
	char dir; // 방향
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;

		q.pop();
		dir = map[x][y]; // map 방향 

		if (dir == 'U') x--;	
		if (dir == 'D') x++;
		if (dir == 'L') y--;
		if (dir == 'R') y++;

		if (x < 0 || y < 0 || x >= n || y >= m) {
			res++;
			return;
		}
		if (!visit[x][y]) {
			visit[x][y] ++;
			q.push(pair<int, int>(x, y));
		}
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			while (!q.empty()) q.pop();  // 큐안에 남아있다면 비우기
			memset(visit, 0, sizeof(visit)); // 방문 배열 초기화
			q.push(pair<int, int>(i, j));
			bfs();

		}
	}

	cout << res << endl;
}

newdeal 5년 전 0

안녕하세요.

52줄부터 시작된 2중for문은 (0,0)부터(n-1,m-1)까지 모든 점들에 대해서 bfs를 돌립니다.

하지만 앞의점에서 이미 지금의 점을 방문했다면, 지금의 점은 bfs를 돌릴 필요가 없지 않을까요?

예를들어 (0,0)에서 (0,1)을지나 25000정도의 길을 거쳐 미로를 탈출했다면, (0,1)은 다시 25000 여 번의 bfs서칭 없이도, 이미(0,0)에서 지금의 점을

방문했다는 점만 안다면 불필요한 bfs 서칭 시간을 줄일 수 있습니다.

더불어 이러한 방문체크를 로그의시간으로 해결한다면 문제를 해결하실 수 있습니다.

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

문제

문제

출처

ICPC

시간 초과 ... 나네요 뭐가 문제일까요.. 고수님들 ㅠㅠ

ska4773 5년 전 0

newdeal 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말