굥굥

(코드 추가) 문제를 다 풀고 다른 공부하다가 문득 들은 생각인데 어짜피 모든 경로는 정해져 있다. 그리고 도착해야하는 목적지가 모두가 같으므로 도착지에서 각 노드별로 bfs를 모두 돌며 얼마나 떨어져있는지 count 를 전부 계산한다. 그리고 sources에 있는 인덱스별 답만 추출하면 되는 문제였다... 수정해서 돌려보니까 정말정말정말 빨라졌다... 왜 처음엔 이 생각을 못했을까..ㅋㅋ 뿌듯하기도하고 당황스럽기도 하다. 큐를 이용한 너비 우선 탐색으로 문제를 풀었다. 문제를 풀기 전에 어떤 섬이 어느 섬들과 연결되어 있는지에 대한 정보를 먼저 정리하고 시작했다. 입력으로 [[1,2] , [2,3]] 이 주어지면 1 -> 2 2 -> 1, 3 3 -> 2 로 정리된 벡터를 하나 만들었다. ..

처음으로 풀어보는 BFS 문제이다. DFS는 트리나 여러가지 탐색문제에도 많이 사용해봐서 알고 있었는데 BFS는 처음 풀어봄..! 처음에는 그냥 동일하게 재귀로 풀면 되지 않을까? 라고 생각했는데 재귀로 푸니 시간에서 걸리는 문제들이 생긴다. (정확성도 틀린것도 있음 ㅠㅠ) BFS는 가장 빠르게 도착하는 값만 return 하면 된다. 재귀와는 다르게 일을 큐에 한개씩 넣어줬을때 조건을 완료하는 값이 있다면 그 값이 가장 빠르게 도착하는 값이다. (전체 다 탐색할 이유x) 그래서 순서대로 일을 큐에 넣어준다. 찾아보니 가중치라는 개념도 있다고 하는데 상하좌우 모두 동일하게 넣어주면 되어서 여기에는 가중치가 필요하진 않다고 함. (가중치가 필요한 작업은 cost가 존재하는 때 인듯합니다.) 현재..