글 읽기 - 시간초과가 나네요... 어떻게해야 시간단축을 할 수있을까요 ㅠㅠ

tjdvyzl12 3년 전 0

다이나밍 프로그래밍 쪽은 늘 약해서 ㅠㅠㅠ bfs 공부하는데 갑자기 dp가 나와서 몇시간째 고민중인데 못풀고있네요 ㅠㅠㅠ 결과는 잘 나오는거같은데 ..

#include <bits/stdc++.h>
using namespace std;

int n, m;
char _map[504][504];
int _visit[504][504];

vector<pair<int, int>> temp;

bool canFinish[504][504];
bool cantFinish[504][504];

int main()
{
	cin >> n >> m; bool isFinish = false;

	for (int y = 1; y <= n; y++) { //map 알파벳으로 채우기
		string input;
		cin >> input;
		for (int x = 1; x <= input.size(); x++) {
			_map[y][x] = input[x - 1];
		}
	}

	queue<pair<int, int>>q;
	
	int cnt = 0;

	for(int y = 1; y <= n ; y++){
		for (int x = 1; x <= m; x++) {
			if (canFinish[y][x] == true) {
				cnt++; continue;
			}
			if (cantFinish[y][x] == true) {
				continue;
			}
			q.push(pair<int, int>(y, x));

			while (q.empty() == false) {
				int cy = q.front().first;
				int cx = q.front().second;;
				q.pop();

				temp.push_back(pair<int, int>(cy, cx));

				_visit[cy][cx]++;

				if (_visit[cy][cx] >= 2) break;
				

				if (cy > n || cx > m || cy < 1 || cx < 1)
				{
					isFinish = true; cnt++; break;
				}

				if (_map[cy][cx] == 'U') {
					q.push(pair<int, int>(cy - 1, cx));
				}
				if (_map[cy][cx] == 'D') {
					q.push(pair<int, int>(cy + 1, cx));
				}
				if (_map[cy][cx] == 'L') {
					q.push(pair<int, int>(cy, cx - 1));
				}
				if (_map[cy][cx] == 'R') {
					q.push(pair<int, int>(cy, cx + 1));
				}
			}
			memset(_visit, 0, 504 * 504 * sizeof(int));

			if (isFinish == true) {
				for (int i = 0; i < temp.size(); i++) {
					canFinish[temp[i].first][temp[i].second] = true;
				}
				temp.clear();
				isFinish = false;
			}
			else {
				for (int i = 0; i < temp.size(); i++) {
					cantFinish[temp[i].first][temp[i].second] = true;
				}
				temp.clear();
			}
		}
	}

	cout << cnt << "\n";
	return 0;
}

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

문제

문제

출처

ICPC

시간초과가 나네요... 어떻게해야 시간단축을 할 수있을까요 ㅠㅠ

tjdvyzl12 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말