글 읽기 - 시간초과나는 이유 뭘까요 BFS로 풀었습니다.

leila000 5년 전 0

다른 사람들꺼랑 비교해도 뭐가 크게 다른지 잘 모르겠어요 ㅠㅠ

어떤부분에서 시간초과가 나는 지 알려주세요

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <vector>

struct pipe {
	int state; // 0 : 가로,  1 : 세로   ,2 : 대각선
	int start_y, start_x, end_y, end_x;
};
// 각  현재 스테이트에 따라서 다음에 가는 스테이트 (dx, dy에 따라)
int state[3][3] = { 0,2,-1,1,2,-1,0,1,2 };

int dx[3][3] = { 1,1,-1,0,1,-1,1,0,1 };
int dy[3][3] = { 0,1,-1,1,1,-1,0,1,1 };
//0의 갈 수 있는 방향 dx[0][0] dx[0][1], dy[0][1] , dy[0][1]...

std::vector<pipe> member;
pipe temp, curr;

int N;
int map[20][20];
int count = 0;

int bfs() {
	int nx, ny;
	temp = { 0,1,1,1,2 };
	member.push_back(temp);

	while (!member.empty()) {
		curr = member.front();
		if ((curr.end_x == N) && (curr.end_y == N)) {
			count++;
			member.erase(member.begin());
			continue;
		}
		for (int i = 0; i < 3; i++) {
			if (dx[curr.state][i] == -1 || dy[curr.state][i] == -1) {
				continue;
			}
			nx = curr.end_x + dx[curr.state][i];
			ny = curr.end_y + dy[curr.state][i];
			if (nx>N || ny>N)
				continue;
			if (map[ny][nx] == 1)
				continue;
			if (state[curr.state][i] == 2) {
				if (map[ny][nx - 1] == 1 || map[ny - 1][nx] == 1) {
					continue;
				}
			}
			temp = { state[curr.state][i] ,curr.end_y,curr.end_x,ny,nx };
			member.push_back(temp);
			
		}
		member.erase(member.begin());

	}
	return count;
}
int main() {
	scanf("%d", &N);
	for (int y = 1; y <= N; y++) {
		for (int x = 1; x <= N; x++) {
			scanf("%d", &map[y][x]);
		}
	}
	count = bfs();
	printf("%d", count);
	return 0;
}

newdeal 5년 전 2

안녕하세요.

54줄의 member.erase(member.begin()); 부분에서

bfs구현하실때 벡터를사용하셨는데 이지점에서 불필요한 N의시간이 소요되는것같습니다.

벡터가 아닌 queue로 구현해보시면 어떨까요?

leila000 5년 전 1

아 그렇네요 ㅠㅠ 벡터 큐로 바꾸니까 바로 맞았습니다 감사합니다 ㅠㅠ

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

문제

문제

출처

ICPC

시간초과나는 이유 뭘까요 BFS로 풀었습니다.

leila000 5년 전 0

newdeal 5년 전 2

leila000 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말