[TIL] 250117

알고리즘

[백준/Python] 17270 연예인은 힘들어

연예인이 아니라 내가 힘들어

 

 

한 문제 푸느라 너무 고생했던 문제. 우선은 이 문제를 푼 사람들이 입을 모아 말할 정도로 문제 조건이 너무...너무.. 더러웠고, 그 문제 조건을 제대로 지켰는지만을 확인하느라 다른 부분의 코드는 당연하게 맞을 거라 생각한게 무수한 틀렸습니다 의 결과를 낳았다.

 

결과적으로 내가 틀렸던 부분은 다익스트라 알고리즘의 설계였고(분명 며칠 전에도 다익스트라 문제를 풀었는데) 더 이상 그래프 최단 거리 알고리즘에 대해 제대로 이해하고 사용하는 걸 미룰 수 없겠다는 생각이 다시 한 번 들었다.

 

다익스트라 알고리즘에서는 각 노드를 한 번씩만 방문한다는 것에 대해 이해를 잘못해서, 우선 순위 큐 자체에 각 노드들이 한 번씩만 들어가도록 코드를 작성해버렸다. 그 결과 해당 노드에 대해 더 짧은 경로를 발견해도 큐에 넣지 못하게 되어서 알고리즘이 제대로 작동하지 않았다.

그러나 큐에 들어가는 것은 방문 예약일 뿐, 확정된 방문이 아니다. 즉, 어떤 노드에 대해 더 짧은 경로가 발견될 때마다 그 노드를 큐에 추가해야 한다. 따라서 실제로는 특정한 노드가 큐에 여러 번 들어갈 수 있으며, 큐에서 꺼낼  해당 노드의 거리가 이미 더 짧은 경로로 처리되었는지를 따져서 방문 여부를 확인해야 한다.

 

ETC

개발 관련 내용은 아니지만.. 최근 들어 한 가장 큰 결심이라 TIL에 남긴다.

드디어 운전 면허 학원에 등록했다!! 쫄보 of 쫄보로서 평생 운전 면허는 딸 일 없을거라 생각했는데 지금 아니면 언제 따겠나..싶어서 등록해버렸다. 사실 지금도 안믿기고 굉장히 걱정 된다. 제가 운전을요?? 제발 이번에 결제한 금액에서 더 추가되는 비용이 없기만을 바랄 뿐이다.

내 뼈에 새겨야될 말