#코딩테스트 #PS #백준 #bakejoon 이번 문제는 BFS 타입이었다. 오는 7월 UCPC 코딩대회에 참가하기 전까지 앞으로 C+PS는 UCPC 기출문제로만 해설해 볼 계획이다.도메인 분석을 확실히 하지 않아 삽질한 문제다. 도메인을 보면 n이 200000까지 올라가고 간선의 총합이 100000을 넘지 않는다. 따라서 n개의 노드가 모두 일직선으로 연결된 경우에 ‘루머를 믿지 않는 모든 노드 주변을 조사’하는 것은 n^2의 시간 복잡도가 걸린다. 이 부분을 뒤늦게 알고 유언비어를 믿는 사람 주변 사람만 조사하는 방식으로 설계를 바꿔 통과했다.Solved.ac 기준 골드4였다. 플래티넘 4→플래티넘 3승급까지 AC.Rating 97점 남았다.<문제>:n명의 사람이 있고, 간선 정보가 주어진다. 각 사람은 주변의 절반 이상이 유언비어를 믿으면 본인도 믿게 된다. 시간이 충분히 지났을 때 각자가 루머를 믿기 시작한 시점을 출력하라.https://www.acmicpc.net/problem/19538문제 당신은 유언비어를 믿나?한 유명 심리학 실험에서는 사람들에게 2개의 행을 보였고 어느 행이 길지를 말해라고 했다. 실제로 한 사람을 제외하고 나머지는 실험자에 의해서 사전에 조작된 사람들이었다. 조작된 사람들은 사실상 더 짧은 줄이 길다고 말했다. 주위의 모두가 똑같은 대답을 하면 진짜 피실험자도 다시 짧은 줄이 길다고 말했다. 이 실험은 사람들이 주위의 사람의 영향을 받음을 보였지만 루머 역시 마찬가지다. 루머는 최초 유포자로부터 시작된다. 최초 유포자는 복수일 가능성이 있으며, 최초 유포자를 제외하고 스스로 르…www.acmicpc.net*문제 유형:그래프로 이론, BFS*체감 난이도…(6/10):도메인 분석을 확실히 한다.-체감 설계 난이도(4/5): 도메인 분석 부분에서 실수를 해서 한번 코드를 다시 칠했다. – 체감 구현 난이도(2/5) : 구현 자체는 무난했다. 1. 바로 해동 성공(최대 30분 고민) 2. 알고리즘 유형을 확인하고 해동 성공 3. 알고리즘 유형을 공부하고 해동 성공 4. 문제 접근 방식을 확인하고 해동 성공(최소한 1시간은 고민해 본다) 5. 업솔빙으로 통과
<코드> / * 백준 1953 8번: 루머… 1트: 2차원 벡터 connect에 간선 정보 저장.1차원 벡터 벨리에프에 i번인이 루머를 믿는 시점을 저장. 루머를 믿는 사람이 더 이상 늘지 않을 때까지 루머를 퍼뜨린다.루머 확산 방법은 connect[i]==-1명, 루머를 믿지 않는 사람 주변에서 루머를 믿는 인원이 belief[i]. size( )+1/2 이상의 값을 가지면 그 사람도 루머를 now_t 시점에서 믿기 시작하도록 갱신. 갱신 여부는 매번 boolischanged에 표시. 더 이상 갱신이 안되면 belief 출력…시간 복잡도 계산?200000*200000까지 간다.
루머를 믿는 사람의 주위사람만 알아보는 방식으로 이야기하자.*/