이차원 배열 이동 문제(자료구조 사용 연습)

                                    1. 각 로봇은 1초에 한칸씩 이동한다
-- 로봇은 좌표차리를 이용하여 r or c로 += 1 씩 이동한다.
---- r먼저 움직이고 c를 움직여야 한다. (우선순위 r > v)

2. r과 c는 x, y 좌표평면과는 다르다 -> 하지만 이를 크게 의식할 필요는 없다.

3. 매 초마다 모든 로봇이 한번씩 움직인다.
-- 모든 로봇이 goal을 했다면 운행을 종료시킨다. while문 + goal
-- 매번 모든 로봇의 경로를 확인 후 겹치는지 체크한다. - 좌표를 체크해보면 된다.

                                    💡 각 로봇에게 고유의 목표를 할당하기?
# n초에 벌어지는 일들
-- 1번째 로봇의 목표위치를 기억
-- 1번째 로봇의 현재위치를 확인
-- 다른 로봇과 겹치는 구간이 있는지 확인
---- 중복 겹침이 일어나지 않도록 로봇 쌍으로 확인
-- 이동 경로 결정
-- 이동
-- 2...n 번째 로봇 모두 반복

-- endCheck이 로봇 수 만큼 나오면 운행 종료
-- 겹치는 구간마다 return값 1씩 증가.

🤔 발생하는 의문점들
모든 로봇의 위치를 따라 관리해서(메모리) 매번 확인?
or
메모리를 안쓰고 확인하는 법?

                                    class Solution {
    fun solution(points: Array<IntArray>, routes: Array<IntArray>): Int {
        var answer: Int = 0
        var endCheck = 0
        var robotCount = routes.size

        // current position update
        var currentPositions: MutableList<Pair<Int,Int>> = mutableListOf()
        var eachGoals: MutableList<Pair<Int, Int>> = mutableListOf()
        for (route in routes) {
            val sR = points[route[0] - 1][0]
            val sC = points[route[0] - 1][1]
            val gR = points[route[route.size - 1] - 1][0]
            val gC = points[route[route.size - 1] - 1][1]
            currentPositions.add(Pair(sR, sC))
            eachGoals.add(Pair(gR, gC))
        }

        // move
        while (endCheck != robotCount) {
            // each time all Robots move!!
            var duplicated: MutableSet<Int> = mutableSetOf()
            for (i in 0 until currentPositions.size) {
                // i robot cur, goal
                var current = currentPositions[i]
                val goal = currentPositions[i]

                // check duplicated
                for (j in i until currentPositions.size) {
                    if (duplicated.contains(j)) break
                    if (current == currentPositions[j]) {
                        duplicated.add(i)
                        duplicated.add(j)
                        answer++
                    }
                }

                // decide moving (r first)
                var currentR = current.first
                var currentC = current.second
                val goalR = current.first
                val goalC = current.second

                // end check first
                if (currentR == goalR && currentC == goalC) {
                    endCheck++
                    break
                }

                if (currentR - goalR != 0) {
                    if (currentR - goalR > 0) {
                        // move to up
                        currentR--
                    }
                    currentR++
                } else if (currentC - goalC != 0) {
                    if (currentC - goalC > 0) {
                        currentC--
                    }
                    currentC++
                }
                // update position
                currentPositions.set(i, Pair(currentR, currentC))
             }
        }

        return answer
    }
}

// r > c 우선순위
// confilctions return
// 100 x 100
// 로봇의 수 = 2~100대
// 각 경로 2~100
// routes = 로봇 수
// routes[0] = [4, 2] -> 1번째 로봇은 points[4- 1] -> points[2 - 1]로 이동한다는 것을 의미.

// (r, c) -> 세로, 가로
// 0초에 충돌하는 것도 고려

//

                                    👉 발생한 오류들

1. route의 중간 경로 탐색 불가
-- route 내부에 목표경로가 여러개 존재하는데 이를 처리하지 못함

gR, gC -> 하나로 고정하면 안돼

2. 좌표 업데이트 미스
-- currenR 이후 바로 currentR을 감소시켜서 오류

3. 불안정적인 duplicated?
-->

                                    💡 다른 자료구조를 사용?

1. 동시간대 겹치는 로봇들을 확인하기 위해 좌표별 로봇의 갯수를 체크
-- 2개 이상인 경우 answer + 1
-- 이후 해시맵 초기화
-- key갑싈 Pair<Int, Int> (좌표)로 설정

2. route의 경우 모든 로봇에 대하여 동일한 크기를 가짐
-- 경로의 수가 일정하므로, for문을 통해 순차적으로 접근하도록 갱신

                                    data class Goal(
    val r: Int,
    val c: Int,
    val idx: Int
)

class Solution {
    fun solution(points: Array<IntArray>, routes: Array<IntArray>): Int {
        var answer: Int = 0
        val robotCount = routes.size
        var routeSize = routes[0].size // for idx check

        // points = [[1, 2]. [1, 3] ... ] point size fixed
        // routes = [[1, 2, 3], [2, 3, 4]]... route -> route - 1 = point's idx
        var currents: MutableList<Pair<Int, Int>> = mutableListOf()
        var goals: MutableList<Goal> = mutableListOf()// [(r, c, idx)]
        var isFinished = BooleanArray(robotCount) {false} // finish check
        var finishCount = 0

        // initinal update
        for (i in 0 until robotCount) {
            val currPair = Pair(points[routes[i][0] - 1][0], points[routes[i][0] - 1][1])
            val initGoal = Goal(
                points[routes[i][1] - 1][0],
                points[routes[i][1] - 1][1],
                1
            )
            currents.add(currPair) // curr position
            goals.add(initGoal)
        }

        while(finishCount < robotCount) {
            var dupMap: MutableMap<Pair<Int, Int>, Int> = mutableMapOf()// {"(r, c)": count}
            for (i in 0 until robotCount) {
                // skip finished robot
                if (isFinished[i]) continue
                var (r, c) = currents[i] // now position
                var (gr, gc, idx) = goals[i] // now goal

                // count dup  - for start ...
                dupMap[Pair(r, c)] = (dupMap[Pair(r, c)] ?: 0) + 1

                // check is goal position?
                if (r == gr && c == gc) {
                    // check is last goal?
                    if (idx == routeSize -1) {
                        isFinished[i] = true
                        finishCount++
                        continue
                    }
                    // find next goal
                    val newGoalPoint = routes[i][idx + 1]
                    val newGoal = Goal(
                        r = points[newGoalPoint - 1][0],
                        c = points[newGoalPoint - 1][1],
                        idx = idx + 1
                    )
                    goals[i] = newGoal
                    gr = goals[i].r // new goal
                    gc = goals[i].c
                }

                // move
                val diffR = r - gr
                val diffC = c - gc

                if (diffR != 0) {
                    if (diffR > 0) {
                        currents[i] = Pair(--r, c)
                    } else {
                        currents[i] = Pair(++r, c)
                    }
                    continue
                } else if (diffC != 0) {
                    if (diffC > 0) {
                        currents[i] = Pair(r, --c)
                    } else {
                        currents[i] = Pair(r, ++c)
                    }
                }
            }

            // check crush (cur)
            for ((pair, cnt) in dupMap) {
                if (cnt >= 2) {
                    answer++
                }
            }
        }

        return answer
    }
}

// r > c 우선순위
// confilctions return
// 100 x 100
// 로봇의 수 = 2~100대
// 각 경로 2~100
// routes = 로봇 수
// routes[0] = [4, 2] -> 1번째 로봇은 points[4- 1] -> points[2 - 1]로 이동한다는 것을 의미.

                                    👉 추가된 로직
1. 현재위치가 goal에 해당한다면, 다음 gaol을 탐색 없다면 finished로 기록
2. 이를 위해서 Goal 클래스를 선언하고 idx를 넣어두었음.

                                    시간 복잡도를 결정 하는 요소들
while, for

✅ while : 모든 경로를 이동할 때까지 반복
이는 routeSize에 해당함

✅ for : 모든 로봇이 한번씩 이동후 여러가지 조건을 체크
이는 robotSize에 해당

큰 틀에서는 routeSize * robotSize 만큼의 시간이 소요된다.

✏️ O(M * N)

                                    결정 요소
map, list(currents, goals)

✅ list
robotSize만큼의 currents와 goals가 할당된다.
currents는 PairInt, Int>, goals는 Goal(Int, Int, Int)

Int = 4Byte로 가정 하면
list에서는 크게 robotSize * 20Byte의 메모리 할당  -> O(N)

✅ map
map은 robotSize만큼 매번 초기화 되므로 -> O(N)

✏️ O(N)

                                    1. Kotlin의 set사용하기

setOf("name", "age")...
mutableSetOf("mutable!!")

                                    1. mapCount

❌ dupMap[Pair(r, c)]?.let {
    dupMap[Pair(r, c)]++
}.else {           // <-- 이 부분이 Kotlin 문법에 없습니다.
    dupMap[Pair(r, c)] = 1
}
- 존재하지 않는 문법
✅  dupMap[Pair(r, c)]?.let {
    dupMap[Pair(r, c)]++
}?: run {dupMap[Pair(r, c)] = 1}

👉 이렇게 사용하기
dupMap[Pair(r, c)] = (dupMap[Pair(r, c)] ?: 0) + 1