글 읽기 - 시간초과 이유를 모르겠습니다 ㅠ

mju6229 5년 전 0

사정상 라이브러리를 사용할 수 없어 구조체배열을 이용하여 bfs를 구현하여 문제를 풀었습니다.

나름 최적화를 했다고 생각하는데 어느부분에서 시간을 많이 사용하는 지 알 수 없어 질문드립니다 ㅠㅠ

어떤 부분을 고치면 시간 안에 문제를 해결할 수 있을까요??

# define _CRT_SECURE_NO_WARNINGS
# include <iostream>

int w, l;
char arr[51][51];
int mem[51][51];
int num, max;

typedef struct {
	int fir;
	int sec;
	int number;
}Land;

Land land[10000];

int main() {
	int i, j, a, b, c, k, p;

	scanf("%d %d", &w, &l);

	for (i = 0; i < w; i++) {
		scanf("%s", arr[i]);
	}

	for (k = 0; k < w; k++) {
		for (p = 0; p < l; p++) {
			mem[k][p] = 1000000;
		}
	}

	for (i = 0; i < w; i++) {
		for (j = 0; j < l; j++) {
			if (arr[i][j] == 'L') {
				land[num].fir = i;
				land[num].sec = j;
				land[num].number = 0;

				while (num >= 0) {
					a = land[num].fir;
					b = land[num].sec;
					c = land[num].number;

					mem[a][b] = c;
					num--;

					if (a - 1 >= 0 && arr[a - 1][b] == 'L' &&  c + 1 < mem[a - 1][b]) {
						num++;
						land[num].fir = a - 1;
						land[num].sec = b;
						land[num].number = c + 1;
					}
					if (a + 1 < w && arr[a + 1][b] == 'L' &&  c + 1 < mem[a + 1][b]) {
						num++;
						land[num].fir = a + 1;
						land[num].sec = b;
						land[num].number = c + 1;
					}
					if (b - 1 >= 0 && arr[a][b - 1] == 'L' && c + 1 < mem[a][b - 1]) {
						num++;
						land[num].fir = a;
						land[num].sec = b - 1;
						land[num].number = c + 1;
					}
					if (b + 1 < l && arr[a][b + 1] == 'L' && c + 1 < mem[a][b + 1]) {
						num++;
						land[num].fir = a;
						land[num].sec = b + 1;
						land[num].number = c + 1;
					}
				}
				for (k = 0; k < w; k++) {
					for (p = 0; p < l; p++) {
						if (max < mem[k][p] && mem[k][p] != 1000000)
							max = mem[k][p];
						mem[k][p] = 1000000;
					}
				}
				num = 0;
			}
		}
	}

	printf("%d\n", max);

	return 0;
}

djm03178 5년 전 1

데이터를 num 쪽에 넣고 num 쪽에서 빼고 있는 것으로 보아 BFS가 아니라 DFS처럼 구현하신 것 같습니다. BFS가 되려면 밑바닥을 가리키는 변수가 하나 더 필요하고, 큐에서 제거할 때는 밑바닥에서 빼내야 합니다.

DFS처럼 구현했을 시의 문제는 기존에 방문한 점까지 도달하기 위해 처음에 이용한 경로보다 나중에 다른 경로를 통해 갔을 때의 거리가 더 짧을 수 있다는 것이고, 그러면 중복 방문이 발생하게 됩니다.

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

문제

문제

출처

ICPC

시간초과 이유를 모르겠습니다 ㅠ

mju6229 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말