List → HashMap으로 변환하여 탐색 시간 최적화

현재 진행 중인 인천공항 지도 제작 프로젝트에서는 수많은 노드(Node)를 지도 위에 배치하고, 그 노드들을 기반으로 path를 연결하여 네비게이션 그래프를 구성한다. 이후 다익스트라 알고리즘을 적용해 최적 경로를 찾는 구조로 되어있다.

나는 프로젝트가 시작된 지 약 1년 후에 투입되었고, 초기 지도 세팅 시 path 연결을 통해 그래프를 구축하는 부분에서 성능 병목이 발생하고 있음을 발견했다. 이 과정에서 노드를 List에 저장하고, 연결된 노드를 매번 순차 탐색하고 있는 비효율적인 코드가 있었음.

🔎 기존 코드 (비효율적)

val nodeList = mutableListOf<Node>()
for (i in nodeList.indices) {
    for (j in 0 until nodeList[i].connectedCount) {
        val link = linkList.pop()
        // 문제가 되는 부분: 매번 전체 리스트 탐색
        val neighbor = nodeList.find { it.index == link.dbId }

        ...
    }
}

• nodeList.find { it.index == link.dbId } 이 부분은 O(n) 복잡도를 가지므로, 노드 수가 많아질수록 성능 저하가 큼.

💡 개선 아이디어

• 노드마다 고유한 식별자인 index가 존재했기 때문에, List 대신 HashMap으로 변환하면 O(1) 시간 복잡도로 탐색 가능하다고 판단.

✅ 개선 코드 (효율적)

// node & node의 dbId를 Map으로 묶어 O(1) 탐색
val nodeMap = nodeList.associateBy { it.index }

for ((index, node) in nodeList.withIndex()) {
    repeat(node.connectedCount) {
        if (linkList.isNotEmpty()) {
            val link = linkList.pop()
            // 실행 시간이 많이 단축된 부분
            val neighbor = nodeMap[link.dbId] // O(1) 탐색

            ...
        }
    }
}

📉 결과: 실행 시간 단축

해쉬맵으로 실행 한 결과 - 10ms

리스트로 실행 한 결과 - 2825ms