글 읽기 - 어느부분에서 문제가 되는지 궁금합니다 도와주세요 고수님들! ㅠ

minerba 5년 전 0

3차원배열로 방향을 저장하면서 탐색하는 것도 고려해봤지만

특정인덱스를 다른방향으로 다시 방문하게 될경우 100*100으로 탐색횟수가 방대해질것 같습니다 ㅠ

그래서 아래 같은방법으로 시도를 했지만 어느부분이 잘못된건지 모르겠네요 ㅠㅠ

#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;

struct DATA {
	int x, y, flg;
}d;

queue<DATA> block;
int w, h, sx, sy, ex, ey;   char a[101][101];
int dx[] = { 1,0,-1,0 };  int dy[] = { 0,1,0,-1 };
int vist[101][101];

void  bfs() {
	while (!block.empty()) {

	/*	for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cout << vist[i][j] << ' ';
			}
			cout << '\n';
		}
		cout << '\n' << '\n'; */

		int x1 = block.front().x; int y1 = block.front().y;
		int flg1 = block.front().flg;
		block.pop();
		if (x1 != sx && y1 != sy && a[x1][y1] == 'C') {
			ex = x1; ey = y1;
			break; 
		}

		for (int i = 0; i < 4; i++) {
			int nx = x1 + dx[i];  int ny = y1 + dy[i];
			if (nx >= 0 && nx < h && ny >= 0 && ny < w) {

				if (i != (flg1 + 2) % 4 && vist[nx][ny] == 0 && a[nx][ny] == '.' || a[nx][ny] == 'C') {  // 반대방향이 아니고 방문했던적이 없던 인덱스이고 빈칸일때 
					if (i == flg1) { // 기존 방향과 같을때 
						vist[nx][ny] = vist[x1][y1]; 
						d.x = nx;
						d.y = ny;
						d.flg = i;
						block.push(d);
					}
					else { // 거울설치로 방향이 바뀌었을때 
						vist[nx][ny] = vist[x1][y1] + 1;
						d.x = nx;
						d.y = ny;
						d.flg = i;
						block.push(d);
					}
				}
			}
		}
	}
	return;
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> w >> h;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> a[i][j];
			if (a[i][j] == 'C') {
				sx = i;
				sy = j;
			}
		}
	}
	vist[sx][sy] = 1;   // 시작지점 방문처리 
	for (int i = 0; i < 4; i++) {
		int nx = sx + dx[i]; int ny = sy + dy[i];
		if (nx >= 0 && nx < h && ny >= 0 && ny < w) {
			if (a[nx][ny] == '.') {
				vist[nx][ny] = 1;
				d.x = nx;
				d.y = ny;
				d.flg = i;
				block.push(d); 
			}
		}
	}
	bfs();
	cout << vist[ex][ey]-1; 

	return 0;
}

adh0463 5년 전 0

저는 3차원 배열을 사용해서 풀엇습니다만, 질문자께서는 어느 부분에서 시간 초과가 난다고 보시는건가요 ??? 방향은 4방향이고, 좌표는 100,100까지니까 재탐색 제외해서 아무리 커봐야 4x100x100 아닌가요 ?

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

문제

문제

출처

ICPC

어느부분에서 문제가 되는지 궁금합니다 도와주세요 고수님들! ㅠ

minerba 5년 전 0

adh0463 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말