프밍노트

https://www.acmicpc.net/problem/15806   통학이 너무나도 하기 싫었던 영우는 결국 학교의 기숙사에 들어갔다. 통학의 고통에서 해방된 기쁨도 잠시, 학교 기숙사에서는 일정 기간마다 청소 검사를 한다는 사실을 알게 되었다. 청소 검사에서 나쁜 점수를 받으면 벌점을 받게 되고, 벌점이 많이 쌓이면 기숙사에서 퇴사 해야 한다. 영우는 어떤 경우에 벌점을 받는지 궁금하여 기숙사에서 진행하는 청소 검사 시스템에 대해 자세히 조사해 보았다. 기숙사 청소 검사 시스템은 오늘로부터 정확히 t 일이 지나고 검사를 하며, 검사 시간 단축을 위해 방의 특정 부분만 검사한다. 하지만 검사하는 특정 부분 중 한 곳이라도 더럽다면 영우는 벌점을 받게 된다. 영우가 사는 방은 N * N 정사각형 방이며..

처음 풀어보는 백준의 플래티넘 문제. 내가 풀었던 방식 부터 적을 생각이다. 우선 문제는 이름 그대로 최단 경로가 아닌 거의 최단 경로를 찾는다. 그래프에서 최단경로들의 간선을 제외한 그다음에 나오는 최단경로를 찾는 문제 우선 생각했던 방법은 다익스트라로 간선들을 지우면서 나간뒤 다익스트라를 한번더 돌릴예정이였다. 그렇게 테스트 하였지만 결과는 8% 실패 실패 이유는 다익스트라로 간선을 지울경우 간선이 하나만 지워지는 문제가 생긴다. 위 의경우 최단경로는 두개로 1 2 4 5 와 1 3 4 5가 있다. 거의 최단경로는 저두개를 제외한 1 ->5인 이여야 하지만 경로를 먼저 지워주게 될경우 4->5가 공유되지않으면서 거의최단경로는 6이 나오게된다. 정상적인경우 위처럼 최단경로들을 제외하여 4->5로가는 길..