개발자는 기록이 답이다

14. 그래프 최단거리(BFS) 예시 입력 1 6 9 1 3 1 4 2 1 2 5 3 4 4 5 4 6 6 2 6 5 예시 출력 1 2 : 3 3 : 1 4 : 1 5 : 2 6 : 2 1번 정점에서 각 정점으로 가는 최소 이동 간선수를 출력하세요. 1번 정점에서 2번정점을 간다고 하면 1->4->6->2 라서 총 3번이다. 1->3->4->6으로 갈 수 도 있지만 4번만에 가서 최단 간선수는 아니다. 1번은 0레벨이고, 1레벨만에 가는건 3,4번이라서 큐에 3,4번이 들어간다. 3,4는 1레벨이고 한번만에 간다는 의미이다. 이런식으로 레벨로 할 수 도 있다 1레벨 돌때, 큐에서 3,4가 나올텐데, for문 2바퀴 돌면서 탐색한다. 3에서 나올 수 있는건 4인데, 이미 체크된거라서 갈 필요 없다. 4에서..

13. 경로탐색(인접리스트, ArrayList) 예시 입력 1 5 9 1 2 1 3 1 4 2 1 2 3 2 5 3 4 4 2 4 5 예시 출력 1 6 정점이 1000개 10000개로 들어온다면 인접행렬로는 비효율적이다. 왜냐하면 정점이 5라고하고 5행 5열로 잡으면 된다. 1번 정점에서 갈 수 있는 정점이 어디인지 탐색하는데, 100개 정도까지는 괜찮지만 1000개 10000개라고 하면 인접행렬이라는 그래프로 할때 10000x10000을 해야해서 메모리를 크게 잡습니다. 그리고 1번 정점에서 갈 수 있는걸 찾으려면 1부터 10000까지 for문을 다 돌아야 합니다. 메모리랑 시간복잡도 면에서 너무 비효율적입니다. 그래서 이럴때 인접리스트를 사용합니다. N이 5라고 가정했을때, 1번 리스트부터 5번 리스..