글 읽기 - c++ 도와주시면 감사합니다 진짜 감사합니다!!ㅜㅜ(주석, 자세한 설명 있어요)

celestial 2년 전 0

일단 제 코드 방식은 다음과 같습니다. 예제를 예로 들자면

5 4

3 1

3 2

4 3

5 3

이면 1에서 3으로 향하도록 vector[1]에 3을 넣습니다.

vector[3] : 4 5 이렇게 들어가겠죠?

처음에는 DFS로 풀었는데 시간초과가 나서 설계를 다시 BFS로 하고, 시간을 줄일 수 있는 개선을 하였습니다.

그 예는 1->3->5 or 1->3->5를 가서 1번 컴퓨터일 때 탐색을 두 번하게 되고

2->3->5 or 2->3->4 이렇게 같은 경로를 반복하게 되는 경우가 발생하니까

hist배열을 만들어서 만일 hist배열에 0 이상의 숫자가 써져 있다면 탐색을 중단하고 루프를 빠져나오도록 만들었습니다.

약간 메모이제이션틱한 컨셉을 최대한 살려보았습니다ㅜ

이렇게 되면 굳이 분기가 쓸데없이 내려가는 현상을 막을 수 있을 거라 생각했는데 이게 오히려 틀렸다고 나오네요.

제 코드에 전반적으로 어떤 문제가 있는지 지적해주셔도 되고, 개선 가르침을 주셔도 환영입니다.

감사합니다!

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define MAX 10001

using namespace std;

int N, M;

vector<int>computer[MAX];
bool visited[MAX];
int hist[MAX] = { -1, };
int maxi = -1;
queue<pair<int, int>>Q;

void BFS() {
	//printf("<<<<<BFS>>>>>\n\n");
	//printf("Q front first : %d second : %d\n\n", Q.front().first, Q.front().second);
	pair<int, int>current;

	while (!Q.empty()) {

		current = Q.front();
		Q.pop();
		//maxi = max(current.second, maxi);

		for (int i = 0; i < computer[current.first].size(); i++) {
			if (!visited[computer[current.first][i]]) {


				//타겟의 최대 깊이가 이미 발견된 경우 
				if (hist[computer[current.first][i]] != -1) {
					
					current.second = 1 + hist[computer[current.first][i]];
					//printf("신규 깊이 : %d 더할 깊이 : %d\n\n", current.second, hist[computer[current.first][i]]);
					//printf("이미 최대 깊이가 발견된 위치(%d)에 접근하였으므로 더 돌 필요 없이 루프를 빠져나옵니다.\n\n",computer[current.first][i]);
					hist[current.first] = current.second;
					
					break;
				}

				//타겟의 최대 깊이가 아직 발견되지 않은 경우
				else {
					//printf("뭔가 할 일이 있는 경우 : <%d>\n\n",current.first);
					hist[current.first] = current.second + 1;
					//printf("hist[%d] : %d\n\n",current.first,hist[current.first]);
				}
				visited[computer[current.first][i]] = true;
				pair<int, int>next;
				next.first = computer[current.first][i];
				next.second = current.second;
				//printf("next first : %d second : %d\n\n", next.first, next.second);
				Q.push(next);
			}
		}
		if (hist[current.first] == -1) {
			//printf("아무것도 안한 경우 : <%d>\n\n", current.first);
			hist[current.first] = current.second;
		}

	}

}


int main() {


	cin >> N >> M;


	for (int i = 0; i < M; i++) {
		int Snode, Tnode;
		cin >> Snode >> Tnode;
		computer[Tnode].push_back(Snode);
	}

	for (int i = N; i >= 1; i--) {

		pair<int,int> start = make_pair(i, 0);
		Q.push(start);
		BFS();
		

	}

	//printf("end!\n\n");

	/*for (int i = 1; i <= N; i++) {
		printf("%d : %d ", i, hist[i]);
	}*/

	int res[MAX];
	int rescnt = 0;

	for (int i = 1; i <= N; i++) {
		if (maxi < hist[i]) {
			maxi = hist[i];
		}
	}
	for (int i = 1; i <= N; i++) {
		if (maxi == hist[i]) {
			res[rescnt++] = i;
		}
	}
	for (int i = 0; i < rescnt; i++) {
		printf("%d ", res[i]);
	}
}

dk10211 2년 전 1

7 5

7 1

6 7

3 2

4 3

5 3

여기서 1번으로 시도하면 (1,6,7) 총 3개가 감염되고 2번으로 시도하면 (2,3,4,5) 총 4개가 감염되는데 1,2라고 출력하네요 그리고 방문배열 초기화도 안하고 계시고 bfs로 구하면 3번컴퓨터로 인해 감염되는 수가 1로 저장되네요

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

문제

문제

출처

ICPC

c++ 도와주시면 감사합니다 진짜 감사합니다!!ㅜㅜ(주석, 자세한 설명 있어요)

celestial 2년 전 0

dk10211 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말