jenlog

🚩 그래프탐색, BFS thinking 1. fail (메모리초과) 처음 풀었을때는 N과 K의 범위가 커서 방문체킹을 인덱스로 접근하는 리스트로 안 만들고 딕셔너리로 만들었는데 메모리 초과가 났다. 구글링해보니, 이렇게 하면 방문했던 노드도 큐에 다시 넣어져서 그렇다고 한다. ⭐ 메모리 초과 발생 이유 : 과거에 했던 값을 계속 처리하기 위해 큐에 값을 넣는 것 때문에 발생함. ex. 10에서 갈 수 있는 노드: 9, 11, 20. but, 10까지 갈 수 있는 방법 엄청 많음. (9->10, 11->10, 5->10 ... ) 2. success 😀 방문체킹 리스트를 인덱스로 접근해 100,001 개의 칸으로 만들어줬다. 칸이 10만개 있어도 아무런 상관없다. 괜히 숫자 커지고 for문 많아지면 쫄게된..