이해가 잘 안되는데, lockTB 초기화는 업데이트 할 때 그 그룹만 False로 다시 바꿔준다는 말인가요??
그럼 그 로직의 의미는 무엇인가요..??
모든 그룹은 업데이트를 결국 할거고, 매 인구 이동마다 초기화되는 lockTB와 같은 역할이 아닌가요???
16234번 - 인구 이동
이해가 잘 안되는데, lockTB 초기화는 업데이트 할 때 그 그룹만 False로 다시 바꿔준다는 말인가요??
그럼 그 로직의 의미는 무엇인가요..??
모든 그룹은 업데이트를 결국 할거고, 매 인구 이동마다 초기화되는 lockTB와 같은 역할이 아닌가요???
기억이 가물해서 정확한 설명인지는 모르겠는데,
Phase 마다 BFS 로 각 노드마다 탐색을 하면서 이미 이번 Phase 에서 방문한 노드는 건너띄는 전략을 취한다는 가정 하에서
한번 연합 A 가 만들어지면 평균치로 조정되고, 다른 국가랑 합쳐지지 않는 한 변하지 않습니다.
A 가 한번 합쳐지고 다음 페이즈에는 그대로라고 합시다.
이때 인근 외부의 연합 B 가 생겨서 수가 조정되면 다시 연합할 여지가 생깁니다.
그러면 외부 인근 국가 B 에서 BFS 로 해서 A 까지 탐색하면 이는 연합이 되는거고 그렇지 않으면 연합이 되지 않습니다.
즉 연합 A 는 탐색할 필요가 없고 외부에서 새로 연합된 것들만 탐색하면 되는 겁니다.
이를 체크하면 빨라진다는 것이 요지입니다.
깔끔하게 이해되었습니다. 시작 조건에서 한 국가에만 인구가 폭발적으로 몰려있는 경우에 탐색할 필요가 없는 국가까지 전부 인접한 그룹이 있는지 확인하는 오버헤드가 있네요
추가 설명 감사합니다.
이해가 안되는데 코드 부탁드려도 될까요ㅠ
위위위 댓글처럼 lockTB 배열의 어느부분을 false로 바꿔야 하는지 모르겠습니다.
특정 국가가 평균치로 업데이트되면 해당 국가에서는 탐색을 시작하지 않아도 된다는 것은 이해했습니다.
해당 국가의 특정 땅[i][j]에서 탐색을 시작하는 경우는 고려할 필요가 없고, 외부에서 시작해 해당 국가로 들어오는 경우만 체크하면 되는 것으로 이해했습니다.
구글링 해보고 유튜브로 찾아봐도 PyPy나 다른 언어로 통과한 코드 밖에 없어서 물어볼 곳이 여기밖에 없네요... 제발 도와주세요ㅠㅠ
기억이 안 나시면 통과한 코드라도 첨부해주시면 정말 감사할것 같습니다ㅠㅠㅠ
혹시 해서 참고하였는데 이미 -1해줬네요..
다른 부분에서 시간초과가 뜨는 것 같은데 역시.. 저의 실력이 부족한가 봅니다 ㅠ.ㅠ
댓글을 작성하려면 로그인해야 합니다.
dh0450 4년 전 9
탐색을 할 때 보통 ```visitTB[]``` 같은걸 두어서 중복체크를 하잖아요?
그리고 한번 phase 가 끝나면 초기화를 하구요.
여기에 더해서 ```lockTB[]``` 같은걸 두는 겁니다.
한번 탐색시에 true 로 바꾸고, Phase 시 초기화를 하지 않고 계속 true 로 둬요.
그리고 특정 그룹에 인구이동이 일어나서 평균 값으로 업데이트 할 때 ```lockTB[]``` 를 false 로 초기화를 시켜요.
그리고 ```visitTB[]``` 처럼 ```lockTB[]``` 가 true 이면 탐색을 하지 않는겁니다.
그러면 불필요한 탐색 오버헤드가 없어지니까 80퍼에서 스무스하게 넘어갑니다.
아마도 100000, 1 이런 두 값이 연속되게 있고, 나머지는 인구이동을 안하는 그런 예제가 80퍼에서 있는듯합니다.