14868번 - 문명
어느 부분이 틀렸을까요?? 너무 많이 틀려서 하루종일 우울합니다ㅠ 제 코드의 로직은 총 문명의 수 k에서 합처질때 마다 하나씩 빼서 k가 1이되는 순간 얼마나 시간이 걸리는지를 확인하는 것입니다.
(숫자는 문명의 이름, x,y는 빈칸)
12처럼 문명이 붙어있는 경우는 disjoint set을 이용해서 미리 합쳐주고 k에서도 빼줍니다.
1x2처럼 문명이 한칸을 간격을 두고 있는 경우는 bfs를 이용하여 문명이 정착한 시간을 ti배열에 기록해줍니다.
000(초기) -> 010(1의 문명을 bfs를 돌립니다) -> 010(2의 문명을 bfs를 돌리는데 x에서 1과 만납니다.) 여기서 x의 ti배열에 기록되어 잇는 값이 두문명이 통합된 시간입니다.
1xy2처럼 문명이 두칸을 간격을 두고 있는 경우도 똑같이 bfs를 이용하여 문명이 정착한 시간을 ti배열에 기록해줍니다.
0000(초기)->0100(1의 문명을 bfs를 돌립니다)->0110(2의 문명을 bfs를 돌립니다 여기서 1의문명이 스치지만 일단 넘어갑니다)->0110(y에서 1의문명과 2의 문명이 겹치는데 이때 y에 기록되어 있는 ti 값이 두명이 통합된 시간입니다.)
댓글을 작성하려면 로그인해야 합니다.
sm970124 4년 전
어느 부분이 틀렸을까요?? 너무 많이 틀려서 하루종일 우울합니다ㅠ 제 코드의 로직은 총 문명의 수 k에서 합처질때 마다 하나씩 빼서 k가 1이되는 순간 얼마나 시간이 걸리는지를 확인하는 것입니다.
(숫자는 문명의 이름, x,y는 빈칸)
12처럼 문명이 붙어있는 경우는 disjoint set을 이용해서 미리 합쳐주고 k에서도 빼줍니다.
1x2처럼 문명이 한칸을 간격을 두고 있는 경우는 bfs를 이용하여 문명이 정착한 시간을 ti배열에 기록해줍니다.
000(초기) -> 010(1의 문명을 bfs를 돌립니다) -> 010(2의 문명을 bfs를 돌리는데 x에서 1과 만납니다.) 여기서 x의 ti배열에 기록되어 잇는 값이 두문명이 통합된 시간입니다.
1xy2처럼 문명이 두칸을 간격을 두고 있는 경우도 똑같이 bfs를 이용하여 문명이 정착한 시간을 ti배열에 기록해줍니다.
0000(초기)->0100(1의 문명을 bfs를 돌립니다)->0110(2의 문명을 bfs를 돌립니다 여기서 1의문명이 스치지만 일단 넘어갑니다)->0110(y에서 1의문명과 2의 문명이 겹치는데 이때 y에 기록되어 있는 ti 값이 두명이 통합된 시간입니다.)