🤔 왜 풀지 못했을까?
위상정렬은 나름 자신있다고 생각하고 있었다. 많은 문제를 풀어보기도 했고 acm craft는 기본 문제라고 생각해서 풀지 않고 있었는데, 오늘 생각이 나서 풀어보았다. 나는 time이라는 전역변수 하나만으로도 문제가 쉽게 해결 될 것이라 생각했지만, 그렇지 않았다. 고려해야 할 사항이 꽤 많아지고 뇌절을 하고 말았다...
처음에는 bfs로 처음 시작하는 노드를 고르고, 전역변수 time을 선언해 계속해서 값들의 최고 값을 큐에 같이 넣어 갱신하는 식으로 했지만, 나는 노드를 0이 아닐때 시간 값이 더 커지는 것을갱신해 줄 수 없었다.
내가 통과 하지 못한 예시이다.
1
10 11
10 20 30 40 50 60 70 80 90 100
1 2
2 3
3 6
6 9
5 4
4 7
7 8
8 9
4 9
10 7
4 3
9
답: 340
나의 출력: 330이런 그래프의 그림을 그려 본다면 노드 7은 170이 아니라 160으로 고정되서 170이 되지 않게 된다....
그래서 방법을 고민하던 중에 배열을 선언해서 값을 저장해야 겠다고 생각했고, 동시에 전역변수도 같이쓰게 되었다. 하지만 계속해서 방법이 틀려서 결국 답을 보게 되었다.
전역변수를 빼고 배열을 선언하는 식으로만 구현하면 바로 풀이가 가능했다..
bfs도 사용하지 않아도 되고 큐마다 시간 값을 갱신해줄 필요가 없다. 나중에 시간 값만 더해주면 되기 때문이다.
😭 구체적으로 고민이 필요하다.
쉬운 문제라고 생각해서 무작정 코드를 작성하면 거의 이런 문제가 발생하는 것 같다.. 꼭 고민을 하고 알고리즘을 검증을 하는 과정을 거쳐야 되는 것 같다..
이런 종류의 문제를 시험에서 안 만나서 다행이라고 생각이 든다... 분명 시험이었다면 뇌절 했겠지 ㅠ
지금 확실하게 공부해 두고 두번 나올 때는 배열을 선언하는 방법을 고려해 봐야 겠다.
파이썬 정답 코드 이다.
https://github.com/Deserve82/KK_Algorithm_Study/blob/master/Kangho/BOJ_1005.py
