글 읽기 - c++ 시간초과가 나옵니다.;;

shdudtjr77 4년 전 0

시간 초과를 어찌 해결해야 할지 모르겠습니다.
#include<iostream>
#include<string>
#include<queue>
using namespace std;
int main() {
	int x, y;
	cin >> x >> y;
	int** visit = new int* [x + 2];
	int** dfs = new int* [x + 2];
	
    string* land = new string[x];


	//미로 생성
	for (int i = 0; i < x; i++) {
		cin >> land[i];
	}


	//각 위치에서의 최단거리 값을 가진 visit배열과 land값으 정화 시킨 이차원 배열 p
	for (int i = 0; i < x + 2; i++) {
		dfs[i] = new int[y + 2];
		
		visit[i] = new int[y + 2];

		for (int j = 0; j < y + 2; j++) {
			if ((i == 0 || j == 0)) {
				visit[i][j] = 1;
				dfs[i][j] = 0;
			}
			else if ((i == x + 1 || j == y + 1)) {
				visit[i][j] = 1;
				dfs[i][j] = 0;
			}
			else {
				visit[i][j] = 0;
			}

		}
	}
	
	queue<int>q,p;
	for (int i = 0; i < x; i++) {
		for (int j = 0; j < y; j++) {

			dfs[i + 1][j + 1] = (land[i][j] - '0');
			if (dfs[i + 1][j + 1] == 1) {
				dfs[i + 1][j + 1] = 0;
				
			}
			else {
				dfs[i + 1][j + 1] = 1;
				
			}
			
		}

	}
	dfs[1][1] = 2;
	q.push(1);
	p.push(1);
	int a=1;
	int b=1;
	queue<int> s, d;
	while (!q.empty()) {
		a = q.front();
		b = p.front();
		q.pop();
		p.pop();
		if (dfs[a + 1][b] == 0 && visit[a + 1][b] == 0&&visit[a][b]!=2) {
			dfs[a + 1][b] = dfs[a][b] + 1;
			visit[a + 1][b] = 2;
			if (dfs[a + 1][b + 1] != 0 || dfs[a + 1][b - 1] != 0 || dfs[a + 2][b] != 0) {
				s.push(a + 1);
				d.push(b);
			}
			//cout << a + 1 << " " << b << " 들어감" << endl;
			
		}

		else if (dfs[a + 1][b] == 1 && visit[a + 1][b] == 0  ) {
			dfs[a + 1][b] = dfs[a][b] + 1;
			visit[a + 1][b] = 3;
			q.push(a + 1);
			p.push(b);
			//cout << "2 " << endl;
		}
		else{}
		
		if (dfs[a - 1][b] == 0 && visit[a - 1][b] == 0&& visit[a][b] != 2) {
			dfs[a - 1][b] = dfs[a][b] + 1;
			visit[a - 1][b] = 2;
			if (dfs[a - 1][b - 1] != 0 || dfs[a - 1][b + 1] != 0 || dfs[a - 2][b] != 0) {
				s.push(a - 1);
				d.push(b);
			}
			
			//cout << "3 " << endl;
			
		}
	    else if(dfs[a - 1][b] ==1 && visit[a - 1][b] == 0) {
			dfs[a - 1][b] = dfs[a][b] + 1;
			visit[a - 1][b] = 3;
			q.push(a - 1);
			p.push(b);
			//cout << "4 " << endl;

		}
		else{}
		if (dfs[a][b - 1] == 0 && visit[a][b - 1] == 0&&visit[a][b] != 2) {
			dfs[a][b - 1] = dfs[a][b] + 1;
			visit[a][b - 1] = 2;
			if (dfs[a - 1][b - 1] != 0 || dfs[a + 1][b - 1] != 0 || dfs[a][b - 2] != 0) {
				
				s.push(a);
				d.push(b - 1);
			}
			
			//cout << "5 " << endl;
		}
		else if (dfs[a ][b-1] == 1&& visit[a][b - 1] == 0) {
			dfs[a][b - 1] = dfs[a][b] + 1;
			visit[a][b - 1] = 3;
			q.push(a);
			p.push(b - 1);
			//cout << "6 " << endl;
		}
		if (dfs[a][b +1] == 0 && visit[a][b + 1] == 0&& visit[a][b] != 2) {
			dfs[a][b + 1] = dfs[a][b] + 1;
			visit[a][b + 1] = 2;
			if (dfs[a][b + 2] != 0 || dfs[a - 1][b + 1] != 0 || dfs[a + 1][b + 1] != 0) {
				s.push(a);
				d.push(b + 1);
				//cout << "5 " << endl;
			}
		
		}
		else if (dfs[a][b + 1] == 1 && visit[a][b + 1] == 0) {
			dfs[a][b + 1] = dfs[a][b] + 1;
			visit[a][b + 1] = 3;
			q.push(a);
			p.push(b + 1);
			//cout << "6 " << endl;
		}

		
	}
	int i = 2;
	while (!s.empty()) {
		a = s.front();
		b = d.front();
		p.push(s.front());
		q.push(d.front());
		s.pop();
		d.pop();
		i++;
		//cout << a<<" "<<b<<"왔냐?" <<dfs[a][b]<< endl;
		while (!p.empty()) {
			int z = p.front();
			int c = q.front();
			p.pop();
			q.pop();
			
			if (visit[z+1][c]<=i&&(dfs[z + 1][c] >= dfs[z][c] + 1 ||dfs[z+1][c]==1 )&&visit[z+1][c]!=2) {
				p.push(z+1);
				q.push(c);
				dfs[z + 1][c] = dfs[z][c] + 1;
				visit[z + 1][c]++;
				//cout << z + 1 << " " << c << "여기임" <<dfs[z+1][c]<< endl;
			}
			if (visit[z-1][c]<=i&&(dfs[z-1][c] >= dfs[z][c] + 1 || dfs[z - 1][c] == 1) && visit[z - 1][c] != 2) {
				p.push(z - 1);
				q.push(c);
				dfs[z - 1][c] = dfs[z][c] + 1;
				visit[z - 1][c]++;
				//cout << z -1 << " " << c << "여기임" <<dfs[z-1][c] <<endl;
			}
			if (visit[z][c+1]<=i&&(dfs[z ][c+1] >= dfs[z][c] + 1 || dfs[z ][c+1] == 1) && visit[z ][c+1] != 2) {
				p.push(z);
				q.push(c+1);
				dfs[z][c + 1] = dfs[z][c] + 1;
				visit[z][c + 1]++;
				//cout << z << " " << c+1 << "여기임" <<dfs[z][c+1]<< endl;
			}
			if (visit[z][c-1]<=i&&(dfs[z][c - 1] >= dfs[z][c] + 1 || dfs[z ][c-1] == 1) && visit[z][c - 1] != 2) {
				p.push(z);
				q.push(c - 1);
				dfs[z][c - 1] = dfs[z][c] + 1;
				visit[z][c - 1]++;
				//cout << z << " " << c - 1 << "여기임"<<dfs[z][c-1] << endl;
			}

		}

	}
	if (dfs[x][y]!=1) {
		cout << dfs[x][y]-1 << endl;
	}
	else {
		cout << -1 << endl;
	}

}
wjddydgns99 4년 전 0

bfs 두번 돌아가는 것 같은데, 한번으로 할 수 있습니다.
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

c++ 시간초과가 나옵니다.;;

shdudtjr77 4년 전 0

wjddydgns99 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
