글 읽기 - 질문좀 부탁합니다 !!

taxijjang 4년 전 0

안녕하세요 제가 생각한 알고리즘은 고슴도치와 물의 배열을 각가 만들어 bfs를 돌린 후 소굴의 위,아래,양옆을 비교하여 고슴도치가 더 빠르게 도착하면 고슴도치는 소굴로 갈 수 있다고 하였습니다. 그런데 작은 n사이즈의 tc에서는 잘 돌아가는데 왜 20정도 이상의 tc에서는 프로그램이 무한루프 처럼 돌아가지 않는지 잘 모르겠습니다. 지나가시면서 간단한 조언이라도 부탁드립니다.

#include<iostream>
#include<queue>
#define SIZE 60

using namespace std;

int R, C;

char go[SIZE][SIZE];
char wa[SIZE][SIZE];

bool v1[SIZE][SIZE];
bool v2[SIZE][SIZE];

int x[4] = { -1,0,1,0 };
int y[4] = { 0,1,-0,-1 };
typedef struct Data {
	int x, y;
	char cnt;
}Data;
void gosm() {
	int s_x, s_y;
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (go[i][j] == 'S') {
				s_x = i, s_y = j;
				i = R;
				break;
			}
		}
	}

	queue<Data> q;

	q.push({ s_x,s_y, '1' });

	while (!q.empty()) {
		int h_x = q.front().x;
		int h_y = q.front().y;
		int h_c = q.front().cnt;
		go[h_x][h_y] = h_c;
		q.pop();
		v1[h_x][h_y] = true;
		for (int i = 0; i < 4; i++) {
			int n_x = h_x + x[i];
			int n_y = h_y + y[i];
			char n_c = h_c + 1;

			if (v1[n_x][n_y] == true)
				continue;
			if (n_x < 1 || n_y < 1 || n_x >R || n_y >C)
				continue;
			if (go[n_x][n_y] == '*' || go[n_x][n_y] == 'X'|| go[n_x][n_y] == 'D')
				continue;

			q.push({ n_x,n_y,n_c });
		}
	}

	getchar();
}

void water() {
	queue<Data> q;
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (wa[i][j] == '*')
				q.push({ i,j,'1' });
		}
	}

	while (!q.empty()) {
		int h_x = q.front().x;
		int h_y = q.front().y;
		int h_c = q.front().cnt;
		wa[h_x][h_y] = h_c;
		q.pop();
		v2[h_x][h_y] = true;
		for (int i = 0; i < 4; i++) {
			int n_x = h_x + x[i];
			int n_y = h_y + y[i];
			char n_c = h_c + 1;

			if (v2[n_x][n_y] == true)
				continue;
			if (n_x < 1 || n_y < 1 || n_x >R || n_y >C)
				continue;
			if (wa[n_x][n_y] == '*' || wa[n_x][n_y] == 'X' || wa[n_x][n_y] == 'D')
				continue;
			q.push({ n_x,n_y,n_c });
		}
	}
}

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

	cin >> R >> C;

	int d_x, d_y;
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			cin >> go[i][j];
			wa[i][j] = go[i][j];
			if (go[i][j] == 'D')
				d_x = i, d_y = j;
		}
	}

	gosm();

	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			cout << go[i][j] << " ";
		}
		cout << "\n";
	}

	water();

	bool toggle = false;
	int min_cnt = 2e9;
	for (int i = 0; i < 4; i++) {
		int n_x = d_x + x[i];
		int n_y = d_y + y[i];

		if (go[n_x][n_y] != '.' && go[n_x][n_y] != 'X' && go[n_x][n_y] != '*') {
			if (wa[n_x][n_y] == '.' || go[n_x][n_y] < wa[n_x][n_y]) {
				toggle = true;
				min_cnt = go[n_x][n_y] - '0';
			}
		}
	}

	if (toggle)
		cout << min_cnt;
	else
		cout << "KAKTUS";
}

sait2000 4년 전 1

큐에 넣을 때 v1같은 데 표시를 해야 합니다. 꺼낼 때 하면 안 됩니다.

sait2000 4년 전 1

지금 대로면 똑같은 점이 여러번 들어갑니다. 그러면 그 똑같은 점들이 또 똑같은 점을 여러번 넣어서 매우 오래 걸리게 됩니다.

taxijjang 4년 전 0

아 그런가요.. 한번 해보겠습니다. 감사합니다 ㅎㅎ 하고 댓글 남기도록 하겠습니다 ㅎㅎ

taxijjang 4년 전 0

ㅇ ㅏ 생각보니 q에 넣을때 체킹을 해줘야 하내요 감사합니다 .ㅠㅠ

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

문제

문제

출처

ICPC

질문좀 부탁합니다 !!

taxijjang 4년 전 0

sait2000 4년 전 1

sait2000 4년 전 1

taxijjang 4년 전 0

taxijjang 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말