1043번 거짓말 (1) 썸네일형 리스트형 [백준/C++] 1043번 거짓말 BFS 풀이 문제를 읽고 testcase를 쭉 훑어보니 결국 진실을 알고 있는 사람과 연결되지 않은 사람들로만 구성된 파티를 찾아내는 것으로 인식했다. 먼저 진실을 알고 있는 사람을 queue에 넣고 같은 파티를 edge로 판단했다. 이후 연결된 모든 사람들을 BFS로 미리 찾는 것을 생각했다. 이후 파티 명단을 보면서 아까 BFS를 통해 찾아낸 사람이 1명이라도 있다면 거짓말을 칠 수 없다고 코드를 짜고 실행시켰는데 한번에 통과를 받았다. 알고보니 이 문제는 유니온파인드(분리집합)문제인데 알고나서 문제를 보니 정말 그랬다. 다음에 시간나면 유니온파인드로도 풀어서 풀이를 올려야겠다. #include using namespace std; queue que ; vector party[51] ; int graph[51][.. 이전 1 다음
