[7일차] DFS & BFS (2)

어제에 이어서 같은 내용으로 문제를 풀었다. 오늘은 총 3문제를 풀었다. 첫 번째 문제는 BFS에 관련 문제였다. 그런데 BFS를 구현하는 것이 중요하지는 않았다. 나는 LCA 알고리즘이 뭔지도 모르는 상태로 문제를 풀기 시작했는데, 두 시간 정도 붙잡고 있었음에도 문제를 푸는 게 쉽지 않았다. BFS 과정을 진행하면서 문제를 해결하려고 했었는데 그리 쉽게 되지 않았다. 게시판에도 나 같은 사람이 있길래 글을 확인해보니 LCA 알고리즘을 사용해보라는 댓글이 있어서 냉큼 LCA 알고리즘을 찾아봤다. 진짜 야무진 알고리즘이었다. 내가 구질구질하게 구현하려고 했던 알고리즘이 아주 깔끔하게 구현되어 있었다. 나는 O(logn)의 방법을 상상하지도 못했는데 세상에 똑똑한 사람들 진짜 많다. 백준에서 LCA 알고리즘을 적용하는 문제를 풀어봐야겠다. 

 

두 번째, 세 번째 문제는 MST를 구하는 문제여서 쉽게 풀 수 있을 줄 알았다. 그런데 두 번째 문제는 너무 힘들었다. 우선, 소수점 입력을 받아야 했는데 아무 생각 없이 long long으로 받았다. 그랬더니 그 입력만 이상하게 받아지는 게 아니라 그 뒤의 모든 입력이 씹혔다. 그래서 이 세상의 모든 것이 날 억까하는 줄 알았는데 다 내 잘못이었다^^ 컴퓨터는 거짓말을 하지 않아요~^^ 그리고 MST를 구하기 위해서 Prim 알고리즘을 사용했는데 과정 중에 dist 배열 갱신 방법을 Dijkstra 알고리즘이랑 헷갈려가지고 이상하게 했다. 그래서 총 cost가 너무 크게 나오는 문제가 있었다. 

 

세번째 문제는 다행스럽게도 별 이슈없이 지나갔다. 배열의 크기가 너무 작아서 런타임 에러가 발생하긴 했지만 5분 안에 해결됐다... 휴...

 

삼성 특강을 하면서 점점 강해지는 것 같긴하다. 근데 나보다 강한 사람들이 훨씬 많겠지.