https://www.acmicpc.net/problem/16940
와우~
BFS 스폐셜 저지?
[DFS,BFS] 백준 1260번 BFS와 DFS(C++)
[DFS,BFS] 백준 1260번 BFS와 DFS(C++)
https://www.acmicpc.net/problem/1260BFS와 DFS라는 개념에 대해서 아는가? 예제를 통한 예시를 보여주겠다 먼저 1,2 1,3 1,4 2,4 3,4라는 edge가 있는 경우를 그래프로 나타내보겠다 대략 이렇게 그려져 있다 그
lee-soo.tistory.com
당연히 BFS풀고와봐야겠지
내용은 간단하다
연결된 NODE들에 대해서
올바른 BFS 방법대로 나온 수열인가? 1
아니면 0
예를들어
앞선 예시에 나온
에 대해서는
이런 형태로만 진행되면 된다
(파랑 > 빨강 > 검정 )
즉 1 2 3 4 OR 1 3 2 4
대신 1 4 이렇게 나오면 안되겠지
그래서 내가 먼저 생각한건
첫번째로 수열이 주어졌을때, 그 수열에 해당하는 값과, 그 부모노드의 모든 자식 노드들을 비교해서, 값이 존재 하면 넘기고
값이 존재하지 않으면 0을 출력!
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
bool visited[100001];
using namespace std;
vector<int> v[100001];
int arr[100001];
int pos[100001];
void bfs(int temp);
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 0; i < n - 1; i++)
{
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
if (arr[0] != 1)
{
cout << 0 << "\n";
return 0;
}
bfs(1);
cout << 1 << "\n";
}
void bfs(int temp)
{
queue<int> q;
q.push(temp);
visited[temp] = true;
int count = 0;
int what = 1;
while (!q.empty())
{
int x = arr[count];
count++;
q.pop();
// cout << "x : " << x << "\n";
for (int i = 0; i < v[x].size(); i++)
{
if (!visited[v[x][i]])
{
q.push(v[x][i]);
int sig = 1;
// 여기서 넣는 값을 생각해야한다.
// 넣는 값에 대해서 부모 노드의 크기만큼 모든 arr을 돌아주는 것이다.
for (int j = 0; j < v[x].size(); j++)
{
sig = 1;
// what에 무엇이 들어가야 할까?
// cout << "what : " << what << " ,arr[what] : " << arr[what] << " ,v[x][j] : " << v[x][j] << "\n";
if (arr[what] == v[x][j])
{
break;
}
sig = 0;
}
if (sig == 0)
{
cout << "0\n";
exit(0);
}
visited[v[x][i]] = true;
what++;
}
}
}
}
int sig = 1;
// 여기서 넣는 값을 생각해야한다.
// 넣는 값에 대해서 부모 노드의 크기만큼 모든 arr을 돌아주는 것이다.
for (int j = 0; j < v[x].size(); j++)
{
sig = 1;
// what에 무엇이 들어가야 할까?
// cout << "what : " << what << " ,arr[what] : " << arr[what] << " ,v[x][j] : " << v[x][j] << "\n";
if (arr[what] == v[x][j])
{
break;
}
sig = 0;
}
if (sig == 0)
{
cout << "0\n";
exit(0);
}
그래서 sig를 이용해서 문제 풀었거든
심지어 정답이야
너무 행복해서 그냥 넘기려 했는데
다른사람들 답을 보니까, 얼래 전부 100ms 이하네..? 나는 왜 15배이상 걸린거지...
해서 찾아본 결과
나는 조건문에서 for문을 한번 더 돌기 떄문에 O(n^2)이 걸린 것
저기 위에 보여준 반복문있잖여
쉽고, 제대로 풀기 위해서는
queue에 들어가는 값을 "수열의 입력대로" 들어갈 수 있게 해주고, bfs에서 queue가 들어갈 때, 그 값이 수열의 값과 일치하는가를 비교하면 된다!
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
bool visited[100001];
using namespace std;
vector<int> v[100001];
int arr[100001];
int pos[100001];
void bfs(int temp);
bool compare(int &a, int &b)
{
return pos[a] < pos[b];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 0; i < n - 1; i++)
{
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
for (int i = 0; i < n; i++)
{
cin >> arr[i];
pos[arr[i]] = i;
}
for (int i = 1; i <= n; i++)
{
sort(v[i].begin(), v[i].end(), compare);
}
if (arr[0] != 1)
{
cout << 0 << "\n";
return 0;
}
bfs(1);
cout << 1 << "\n";
}
void bfs(int temp)
{
queue<int> q;
q.push(temp);
visited[temp] = true;
int what = 0;
while (!q.empty())
{
int x = q.front();
q.pop();
if (x != arr[what++])
{
cout << 0 << "\n";
exit(0);
}
// cout << "x : " << x << "\n";
for (int i = 0; i < v[x].size(); i++)
{
if (!visited[v[x][i]])
{
q.push(v[x][i]);
visited[v[x][i]] = true;
}
}
}
}
이게 무슨말인가 싶을거다
먼저,
for (int i = 0; i < n; i++)
{
cin >> arr[i];
pos[arr[i]] = i;
}
for (int i = 1; i <= n; i++)
{
sort(v[i].begin(), v[i].end(), compare);
}
이부분을 보면 알 수 있는게
pos는 당연히, 해당 값이 저장된 index 값을 가지고 있는 것이고?
sort를 통해서
벡터에 들어간 값들에 대해
v[i]내부에 있는 값들이 전부 ,
pos의 위치대로 정렬되는 것이다.
예를들어
4
1 2
1 3
2 4
1 2 3 4
이런 입력이 주어졌다고 했을 떄
pos[1] = 1
pos [2] =2
pos [3] =3
pos[4] =4이고
각 v[i]에 대해서 볼때
v[1]은 2,3을 갖고있는데
2라는 값이, 수열 에서 3보다 앞에있잖아?
즉 v[1][0]=2 v[1][1]=3으로 정렬되는거야
근데 이미 저렇게 되어있는거 아니냐고
1,3
1,2
입력이 이렇게 들어오면 순서가 엉망진창이되니까 그런거임
쨋든 이렇게 해놓고 bfs 쪽을보자
what=0으로시작해서
int x = q.front();
q.pop();
if (x != arr[what++])
{
cout << 0 << "\n";
exit(0);
}
이런게 생겼지?
이게 왜 말이 되는 거냐면
먼저, queue의 값이 들어오는 것을 생각하면 이제 arr의 순서대로 들어올 것이다
왜냐?
앞에서 미리 v[i]의 모든 값들을 arr순서대로 정렬해놓았기때문에
그래서 각 x를 부모노드로 칭할때, 그 값은 당연하게도 arr[what]의 값하고 같아야 되는 것이다
예를들어
4
1 3
1 2
2 4
1 2 3 4
란 값이 들어올때를 보자
부모노드의 경우 미리 visited를 통해 삭제되니 vector안에는 존재하나, 표현하진않음
여기서 정렬을 하게 되면
1 vector 안에 있는 값이 저렇게 바뀐다.
이후 먼저
q.front() 1==arr[0]은 당연하니 넘어가고.
queue에는, 1의 연결된 노드들에 관하여 2,3이 쌓인다.
그 다음 front를 볼때 1에 arr순서대로 정렬된 애들은 2,3이다.
그렇다면 2가 front로 나오면 당연히 arr의 index와 같은게 보장이 된다
(예를들어 정렬이 안되어있으면 q에 들어가는 순서는 3,2일 것이다, 왜냐면 1,3 에서 v[1]의 맨 앞에는 3이 들어오기 때문)
2가끝날때
이후 2,3이 끝난다면 당연히 2가 부모노드일때 4가 들어왔고 3이 부모노드일때는 아무것도 안들어왓으니
4가 시작된다.
...
실행시간이 확연히 줄어들었따~
