[백준 BOJ][C++]16940번 BFS 스페셜 저지 풀이: BFS

https://www.acmicpc.net/problem/16940

16940번: BFS 스페셜 저지

 

 처음 풀이에선, 입력으로 주어진 순서에 따라 해당 노드에서 연결된 노드들 중 현재 순서인 노드를 찾는 반복문을 돌렸더니 시간초과가 떴습니다 ㅠ 

 시간초과를 해결하기 위해선 그래프 내의 연결된 노드들을 순서에 맞게 정렬 후, bfs를 실행해야 하는 것을 발견했습니다.

 

 

 

 

[변수 설명]

 

1. vector<int> graph[MAX] : 그래프 정보, graph[u] = 노드 u에 연결된 노드들

2. order[MAX]: 각 노드의 순서, order[x] = 노드 x의 순서

3. visit[MAX]: 각 노드의 방문 여부, visit[x] = 노드 x의 방문 여부 true/false

4. bfs() 내부의 seq: 탐색 과정에서 현재 방문 순서

 

 

 

[풀이 과정]

 

1. 입력받은 노드 정보로 graph를 완성합니다. 

2. 각 노드들의 순서를 나타내는 order를 완성합니다. 

3. order에 저장된 정보를 보고 graph[i] 안의 노드들을 정렬합니다. 

4
1 2
1 3
2 4
1 3 2 4

order[x]	order[1]	order[2]	order[3]	order[4]
순서	1	3	2	4

graph[1]	graph[2]	graph[3]	graph[4]
{3, 2}	{1, 4}	{1}	{2}

 

4. bfs()를 호출합니다. 

5. 노드 1을 방문 표시 후, queue에 푸시합니다. 

6. queue의 front 노드를 팝하여 다음 노드를 탐색합니다.

7. 현재 노드에 연결된 노드 들 중, 아직 방문하지 않았고 order[next] == seq인 노드를 방문 표시후, queue에 푸시합니다.  order[next] != seq 라면 입력으로 주어진 방문 순서가 BFS 방문 순서에 적합하지 않은 것이므로 그 즉시 false를 반환합니다. 

8. queue가 empty일 때까지 6~7 과정을 반벅합니다. 

 

 

 

 

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>

using namespace std;

#define MAX 100001

int n;
vector<int> graph[MAX];
int order[MAX];
bool visit[MAX];

bool bfs() {

	queue<int> q;
	int seq = 2;

	visit[1] = true;
	q.push(1);

	while (!q.empty()) {
		int curr = q.front();
		q.pop();

		for (int i = 0; i < graph[curr].size(); i++) {
			int next = graph[curr][i];
			if (visit[next])
				continue;

			if (!visit[next] && order[next] == seq) {
				visit[next] = true;
				seq++;
				q.push(next);
			}
			else if (order[next] != seq)
				return false;
		}
	}
	return true;
}

bool comp(const int& a, int& b) {
	return order[a] < order[b];
}

int main(void) {

	cin >> n;

	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		order[x] = i;
	}

	for (int i = 1; i <= n; i++) {
		sort(graph[i].begin(), graph[i].end(), comp);
	}

	cout << bfs();

	return 0;
}