글 읽기 - 3퍼센트에서 시간초과... 고수님들 도와주세요ㅜㅜ

fantasy7772 2년 전 0

예제나 여러 반례들은 해보았는데 정담으로 나옵니다. 그렇지만 3퍼센트에서 계속 시간초과로 나오는데 어느 부분이 문제일까요ㅠㅠ 방문처리 및 횟수가 10이 넘어가면 -1 return을 해주어도 그렇게 되네요. 도와주시면 감사하겠습니다!

#include<iostream>
#include<queue>
using namespace std;
int N, M;
int answer = 0x3f3f3f;
bool visit[11][11][11][11] = { false, };
queue <pair<pair<int, int>, int>> R;
queue <pair<pair<int, int>, int>> B;
char MAP[11][11];
void input() {
	cin >> N >> M;
	int ry, rx, by, bx;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> MAP[i][j];
			if (MAP[i][j] == 'R') {
				R.push(make_pair(make_pair(i, j), 0));
				ry = i;
				rx = j;
			}
			if (MAP[i][j] == 'B') {
				by = i;
				bx = j;
				B.push(make_pair(make_pair(i, j), 0));
			}

		}
	}
	visit[ry][rx][by][bx] = true;
}

void m_left(int Rcy, int Rcx, int Bcy, int Bcx, int cnt) {
	int nry = Rcy;
	int nrx = Rcx;
	int nby = Bcy;
	int nbx = Bcx;
	while (MAP[nry][nrx -1] != '#' && MAP[nry][nrx-1] != 'O') {
		nrx--;
	}
	if (MAP[nry][nrx - 1] == 'O') {
		nrx--;
	}

	while (MAP[nby][nbx - 1] != '#' && MAP[nby][nbx - 1] != 'O') {
		nbx--;
	}
	if (MAP[nby][nbx - 1] == 'O') {
		nbx--;
	}

	if (MAP[nby][nbx] == 'O') return;

	if (nry == nby && nrx == nbx) {//겹쳤을때 
		if (MAP[nry][nrx] == 'O') return;
		else {
			if (Bcx > Rcx) {
				nbx = nbx + 1;
				while (MAP[nby][nbx] != '.') {
					nbx++;
				}
			}
			else {
				nrx = nrx + 1;
				while (MAP[nby][nbx] != '.') {
					nrx++;
				}
			}
		}
	}
	if (MAP[nby][nbx] == 'O') {
		return;
	}
	if (visit[nry][nrx][nby][nbx]) return;
	visit[nry][nrx][nby][nbx] = true;
	R.push(make_pair(make_pair(nry, nrx), cnt + 1));
	B.push(make_pair(make_pair(nby, nbx), cnt + 1));
}


void m_right(int Rcy, int Rcx, int Bcy, int Bcx, int cnt) {
	int nry = Rcy;
	int nrx = Rcx;
	int nby = Bcy;
	int nbx = Bcx;
	while (MAP[nry][nrx + 1] != '#'&& MAP[nry][nrx + 1] != 'O') {
		nrx++;
	}
	if (MAP[nry][nrx + 1] == 'O') {
		nrx++;
	}

	while (MAP[nby][nbx + 1] != '#' && MAP[nby][nbx + 1] != 'O') {
		nbx++;
	}
	if (MAP[nby][nbx + 1] == 'O') {
		nbx++;
	}

	if (MAP[nby][nbx] == 'O') return;
	if (nry == nby && nrx == nbx) {
		if (MAP[nry][nrx] == 'O') return;
		else {
			if (Bcx > Rcx) {
				nrx = nrx - 1;
				while (MAP[nby][nbx] != '.') {
					nrx--;
				}
			}
			else {
				nbx = nbx - 1;
				while (MAP[nby][nbx] != '.') {
					nbx--;
				}
			}
		}
	}
	if (MAP[nby][nbx] == 'O') {
		return;
	}
	if (visit[nry][nrx][nby][nbx]) return;
	visit[nry][nrx][nby][nbx] = true;
	R.push(make_pair(make_pair(nry, nrx), cnt + 1));
	B.push(make_pair(make_pair(nby, nbx), cnt + 1));
}


void m_down(int Rcy, int Rcx, int Bcy, int Bcx, int cnt) {
	int nry = Rcy;
	int nrx = Rcx;
	int nby = Bcy;
	int nbx = Bcx;
	while (MAP[nry+1][nrx] != '#' && MAP[nry+1][nrx]!='O') {
		nry++;
	}
	if (MAP[nry+1][nrx] == 'O') {
		nry++;
	}

	while (MAP[nby+1][nbx] != '#'&& MAP[nby+1][nbx]!='O') {
		nby++;
	}
	if (MAP[nby+1][nbx] == 'O') {
		nby++;
	}

	if (MAP[nby][nbx] == 'O') return;
	if (nry == nby && nrx == nbx) {
		if (MAP[nry][nrx] == 'O') return;
		else {
			if (Bcy > Rcy) {
				nry = nry - 1;
				while (MAP[nby][nbx] != '.') {
					nry--;
				}
			}
			else {
				nby = nby - 1;
				while (MAP[nby][nbx] != '.') {
					nby--;
				}
			}
		}
	}
	if (MAP[nby][nbx] == 'O') {
		return;
	}
	if (visit[nry][nrx][nby][nbx]) return;
	visit[nry][nrx][nby][nbx] = true;
	R.push(make_pair(make_pair(nry, nrx), cnt + 1));
	B.push(make_pair(make_pair(nby, nbx), cnt + 1));
}


void m_up(int Rcy, int Rcx, int Bcy, int Bcx, int cnt) {

	int nry = Rcy;
	int nrx = Rcx;
	int nby = Bcy;
	int nbx = Bcx;
	while (MAP[nry - 1][nrx] != '#'&& MAP[nry-1][nrx]!='O') {
		nry--;
	}
	if (MAP[nry - 1][nrx] == 'O') {
		nry--;
	}

	while (MAP[nby - 1][nbx] != '#'&& MAP[nby-1][nbx]!='O') {
		nby--;
	}
	if (MAP[nby - 1][nbx] == 'O') {
		nby--;
	}
	
	if (nry == nby && nrx == nbx) {
		if (MAP[nry][nrx] == 'O') return;
		else {
			if (Bcy > Rcy) {
				nby = nby + 1;
				while (MAP[nby][nbx] != '.') {
					nby++;
				}
			}
			else {
				nry = nry + 1;
				while (MAP[nry][nrx] != '.') {
					nry++;
				}
			}
		}
	}

	if (MAP[nby][nbx] == 'O') {
		return;
	}
	if (visit[nry][nrx][nby][nbx]) return;
	visit[nry][nrx][nby][nbx] = true;
	R.push(make_pair(make_pair(nry, nrx), cnt + 1));
	B.push(make_pair(make_pair(nby, nbx), cnt + 1));
}

int solve() {
	while (!R.empty()||!B.empty()) {
		int Rcy = R.front().first.first;
		int Rcx = R.front().first.second;
		int Rcnt = R.front().second;
		R.pop();

		int Bcy = B.front().first.first;
		int Bcx = B.front().first.second;
		int Bcnt = B.front().second;
		B.pop();
		if (Rcnt > 10) {
			return -1;
		}
		if (MAP[Rcy][Rcx] == 'O' && MAP[Bcy][Bcx] != 'O') {
			return Rcnt;
		}
		
		m_left(Rcy, Rcx, Bcy, Bcx, Rcnt);
		m_right(Rcy, Rcx, Bcy, Bcx, Rcnt);
		m_down(Rcy, Rcx, Bcy, Bcx, Rcnt);
		m_up(Rcy, Rcx, Bcy, Bcx, Rcnt);
	}

	return -1;
	
}

int main() {
	input();
	cout<<solve();
}

fantasy7772 2년 전 0

53번째의 '겹쳤을때' 부분을 처리해주는 if 문의 58번 라인과 64번 라인의 조건을

while (MAP[nby][nbx] != '.') 이 아닌 while (MAP[nby][nbx] == '#')로 처리해주니까

맞췄습니다로 바뀌었는데 이유를 잘 모르게씁니다 ㅠㅠㅠ

#include<iostream>
#include<queue>
using namespace std;
int N, M;
int answer = 0x3f3f3f;
bool visit[11][11][11][11] = { false, };
queue <pair<pair<int, int>, int>> R;
queue <pair<pair<int, int>, int>> B;
char MAP[11][11];
void input() {
	cin >> N >> M;
	int ry, rx, by, bx;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> MAP[i][j];
			if (MAP[i][j] == 'R') {
				R.push(make_pair(make_pair(i, j), 0));
				ry = i;
				rx = j;
			}
			if (MAP[i][j] == 'B') {
				by = i;
				bx = j;
				B.push(make_pair(make_pair(i, j), 0));
			}

		}
	}
	visit[ry][rx][by][bx] = true;
}

void m_left(int Rcy, int Rcx, int Bcy, int Bcx, int cnt) {
	int nry = Rcy;
	int nrx = Rcx;
	int nby = Bcy;
	int nbx = Bcx;
	while (MAP[nry][nrx -1] != '#' && MAP[nry][nrx-1] != 'O') {
		nrx--;
	}
	if (MAP[nry][nrx - 1] == 'O') {
		nrx--;
	}

	while (MAP[nby][nbx - 1] != '#' && MAP[nby][nbx - 1] != 'O') {
		nbx--;
	}
	if (MAP[nby][nbx - 1] == 'O') {
		nbx--;
	}

	if (MAP[nby][nbx] == 'O') return;

	if (nry == nby && nrx == nbx) {//겹쳤을때 
		if (MAP[nry][nrx] == 'O') return;
		else {
			if (Bcx > Rcx) {
				nbx = nbx + 1;
				while (MAP[nby][nbx] == '#') {
					nbx++;
				}
			}
			else {
				nrx = nrx + 1;
				while (MAP[nby][nbx] == '#') {
					nrx++;
				}
			}
		}
	}
	if (MAP[nby][nbx] == 'O') {
		return;
	}
	if (visit[nry][nrx][nby][nbx]) return;
	visit[nry][nrx][nby][nbx] = true;
	R.push(make_pair(make_pair(nry, nrx), cnt + 1));
	B.push(make_pair(make_pair(nby, nbx), cnt + 1));
}


void m_right(int Rcy, int Rcx, int Bcy, int Bcx, int cnt) {
	int nry = Rcy;
	int nrx = Rcx;
	int nby = Bcy;
	int nbx = Bcx;
	while (MAP[nry][nrx + 1] != '#'&& MAP[nry][nrx + 1] != 'O') {
		nrx++;
	}
	if (MAP[nry][nrx + 1] == 'O') {
		nrx++;
	}

	while (MAP[nby][nbx + 1] != '#' && MAP[nby][nbx + 1] != 'O') {
		nbx++;
	}
	if (MAP[nby][nbx + 1] == 'O') {
		nbx++;
	}

	if (MAP[nby][nbx] == 'O') return;
	if (nry == nby && nrx == nbx) {
		if (MAP[nry][nrx] == 'O') return;
		else {
			if (Bcx > Rcx) {
				nrx = nrx - 1;
				while (MAP[nby][nbx] == '#') {
					nrx--;
				}
			}
			else {
				nbx = nbx - 1;
				while (MAP[nby][nbx] == '#') {
					nbx--;
				}
			}
		}
	}
	if (MAP[nby][nbx] == 'O') {
		return;
	}
	if (visit[nry][nrx][nby][nbx]) return;
	visit[nry][nrx][nby][nbx] = true;
	R.push(make_pair(make_pair(nry, nrx), cnt + 1));
	B.push(make_pair(make_pair(nby, nbx), cnt + 1));
}


void m_down(int Rcy, int Rcx, int Bcy, int Bcx, int cnt) {
	int nry = Rcy;
	int nrx = Rcx;
	int nby = Bcy;
	int nbx = Bcx;
	while (MAP[nry+1][nrx] != '#' && MAP[nry+1][nrx]!='O') {
		nry++;
	}
	if (MAP[nry+1][nrx] == 'O') {
		nry++;
	}

	while (MAP[nby+1][nbx] != '#'&& MAP[nby+1][nbx]!='O') {
		nby++;
	}
	if (MAP[nby+1][nbx] == 'O') {
		nby++;
	}

	if (MAP[nby][nbx] == 'O') return;
	if (nry == nby && nrx == nbx) {
		if (MAP[nry][nrx] == 'O') return;
		else {
			if (Bcy > Rcy) {
				nry = nry - 1;
				while (MAP[nby][nbx] == '#') {
					nry--;
				}
			}
			else {
				nby = nby - 1;
				while (MAP[nby][nbx] == '#') {
					nby--;
				}
			}
		}
	}
	if (MAP[nby][nbx] == 'O') {
		return;
	}
	if (visit[nry][nrx][nby][nbx]) return;
	visit[nry][nrx][nby][nbx] = true;
	R.push(make_pair(make_pair(nry, nrx), cnt + 1));
	B.push(make_pair(make_pair(nby, nbx), cnt + 1));
}


void m_up(int Rcy, int Rcx, int Bcy, int Bcx, int cnt) {

	int nry = Rcy;
	int nrx = Rcx;
	int nby = Bcy;
	int nbx = Bcx;
	while (MAP[nry - 1][nrx] != '#'&& MAP[nry-1][nrx]!='O') {
		nry--;
	}
	if (MAP[nry - 1][nrx] == 'O') {
		nry--;
	}

	while (MAP[nby - 1][nbx] != '#'&& MAP[nby-1][nbx]!='O') {
		nby--;
	}
	if (MAP[nby - 1][nbx] == 'O') {
		nby--;
	}
	
	if (nry == nby && nrx == nbx) {
		if (MAP[nry][nrx] == 'O') return;
		else {
			if (Bcy > Rcy) {
				nby = nby + 1;
				while (MAP[nby][nbx] == '#') {
					nby++;
				}
			}
			else {
				nry = nry + 1;
				while (MAP[nry][nrx] == '#') {
					nry++;
				}
			}
		}
	}

	if (MAP[nby][nbx] == 'O') {
		return;
	}
	if (visit[nry][nrx][nby][nbx]) return;
	visit[nry][nrx][nby][nbx] = true;
	R.push(make_pair(make_pair(nry, nrx), cnt + 1));
	B.push(make_pair(make_pair(nby, nbx), cnt + 1));
}

int solve() {
	while (!R.empty()||!B.empty()) {
		int Rcy = R.front().first.first;
		int Rcx = R.front().first.second;
		int Rcnt = R.front().second;
		R.pop();

		int Bcy = B.front().first.first;
		int Bcx = B.front().first.second;
		int Bcnt = B.front().second;
		B.pop();
		if (Rcnt > 10) {
			return -1;
		}
		if (MAP[Rcy][Rcx] == 'O' && MAP[Bcy][Bcx] != 'O') {
			return Rcnt;
		}
		
		m_left(Rcy, Rcx, Bcy, Bcx, Rcnt);
		m_right(Rcy, Rcx, Bcy, Bcx, Rcnt);
		m_down(Rcy, Rcx, Bcy, Bcx, Rcnt);
		m_up(Rcy, Rcx, Bcy, Bcx, Rcnt);
	}

	return -1;
	
}

int main() {
	input();
	cout<<solve();
}

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

문제

문제

출처

ICPC

3퍼센트에서 시간초과... 고수님들 도와주세요ㅜㅜ

fantasy7772 2년 전 0

fantasy7772 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말