5월 19일 PS일지 #Class 1,2,3 금장

1. Class 3까지 금장

Class 3의 남은 문제들을 전부 해결하므로써 금장을 땄다.

2. 0/1 BFS 기억할만한 요소

https://www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

0/1 BFS 문제로 접근했다. 그리고 0/1 bfs를 그동안 잘못 구현하고 있었다는 사실을 깨달았다.

가중치가 0 또는 1뿐이므로 0의 가중치를 가진 간선을 연결할 때는 dq의 front에, 1의 경우는 dq의 back에 push하는 방법으로 구현하고 나머지는 bfs와 똑같이하면 되는줄 알았는데, push 조건이 달랐다. 

큐에서 정점이 들어있는 순서는 분명히

1 1 1 1 1 2 2 2 2 2 
이런 식으로 거리에 따라 정렬되어 있지만

거리 1인 정점 x가 가중치 0의 간선을 이용해 거리 1인 정점 u를 체크하기 전에
다른 거리 1 정점 v가 u를 거리 2라고 체크해버리면 오류가 생긴다!

따라서 다익스트라처럼 dist[x] + w < dist[u] 면 relax하도록 거리 조건을 넣어줘야 한다.

큐가 정렬되어 있으므로 시간복잡도는 O(V+E)로 동일하다.