궤도

문제 풀이 처음에는 각 사람들의 연결관계를 그래프로 만들어서 dfs했는데 생각해보니 정답을 맞고 보니 유니온 파인드로도 풀 수 있단걸 깨달아서 유니온 파인드로도 풀었다. 두 풀이 모두 중요한 부분은 모든 파티 정보를 고려해서 연결되어 있는 사람들을 전부 찾아야 한다는 것이다. 소스코드 - dfs #include #include using namespace std; vector isLie; //이 사람에게 거짓말을 할 수 있나? vector party_info; //파티 정보 vector graph; //연결 정보 void dfs(int cur) { //거짓말을 할 수 없는 사람을 체크 isLie[cur] = false; for (int i = 0; i < graph[cur].size(); i++) { i..

문제 풀이 myunji.tistory.com/350 [백준] 4803번 : 트리 문제 풀이 트리의 가장 큰 특징은 사이클이 없단 것이다. 이러면 안된다는 뜻이다. 그래서 이번에 새로 방문할 정점이 이전에 방문한 정점인지, 그래서 사이클이 형성됐는지 확인해야 한다. 근 myunji.tistory.com 이 문제에서 사이클을 찾는 코드를 작성하긴 했었다. 근데 이번 문제는 사이클이 생기는 지점을 정확히 찾아야 하기도 하고...해서 유니온 파인드로 풀 것이다. 달리말하면 4803번도 유니온 파인드로 풀 수 있단 뜻이다. 아무튼 유니온 파인드에서 사이클이 형성된다는 것을 알 수 있는 기점은 유니온 하려는 x와 y의 부모가 같을 때이다. 소스코드 #include #include using namespace std..

문제 풀이 myunji.tistory.com/367 [백준] 1717번 : 집합의 표현 문제 풀이 유니온 파인드로 푸는 문제다. 약...2년전 자료구조 시간에 배웠는데 그때 당시에는 아는 것도 없고 + 영어 강의고 + 기타 등등의 이유로 개념만 정말 간신히 익힌 것 같다. 지금 내가 myunji.tistory.com 이 문제랑 거의 유사한데 다만 입력값이 string이라는게 조금 까다로울 뿐이다. string으로 들어온 입력값을 int처럼 사용할 수 있게 map을 사용할 것이다. Fred - 1 Barney - 2 Betty - 3 Wilma - 4 이런식으로 저장하면 parent[4]는 Wilma의 부모 노드인 뭐 그런거다. 소스코드 #include #include #include #include us..

문제 풀이 유니온 파인드로 푸는 문제다. 약...2년전 자료구조 시간에 배웠는데 그때 당시에는 아는 것도 없고 + 영어 강의고 + 기타 등등의 이유로 개념만 정말 간신히 익힌 것 같다. 지금 내가 설명하기엔 ssungkang.tistory.com/entry/Algorithm-%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9CUnion-Find [Algorithm] 유니온 파인드(Union - Find) 유니온 파인드 알고리즘이란? 그래프 알고리즘의 일종으로서 상호 배타적 집합, Disjoint-set 이라고도 합니다. 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 ssungkang.tistory.com 이 분이 정말 완..