03/20 알고리즘 공부(73) - 공원 산책

조건

지나다니는 길을 'O', 장애물을 'X'로 나타낸 직사각형 격자 모양의 공원에서 로봇 강아지가 산책을 하려합니다. 산책은 로봇 강아지에 미리 입력된 명령에 따라 진행하며, 명령은 다음과 같은 형식으로 주어집니다.

• ["방향 거리", "방향 거리" … ]

예를 들어 "E 5"는 로봇 강아지가 현재 위치에서 동쪽으로 5칸 이동했다는 의미입니다. 로봇 강아지는 명령을 수행하기 전에 다음 두 가지를 먼저 확인합니다.

• 주어진 방향으로 이동할 때 공원을 벗어나는지 확인합니다.
• 주어진 방향으로 이동 중 장애물을 만나는지 확인합니다.

위 두 가지중 어느 하나라도 해당된다면, 로봇 강아지는 해당 명령을 무시하고 다음 명령을 수행합니다.
공원의 가로 길이가 W, 세로 길이가 H라고 할 때, 공원의 좌측 상단의 좌표는 (0, 0), 우측 하단의 좌표는 (H - 1, W - 1) 입니다.

공원을 나타내는 문자열 배열 park, 로봇 강아지가 수행할 명령이 담긴 문자열 배열 routes가 매개변수로 주어질 때, 로봇 강아지가 모든 명령을 수행 후 놓인 위치를 [세로 방향 좌표, 가로 방향 좌표] 순으로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한조건

• 3 ≤ park의 길이 ≤ 50
  • 3 ≤ park[i]의 길이 ≤ 50
    • park[i]는 다음 문자들로 이루어져 있으며 시작지점은 하나만 주어집니다.
      • S : 시작 지점
      • O : 이동 가능한 통로
      • X : 장애물
  • park는 직사각형 모양입니다.
• 1 ≤ routes의 길이 ≤ 50
  • routes의 각 원소는 로봇 강아지가 수행할 명령어를 나타냅니다.
  • 로봇 강아지는 routes의 첫 번째 원소부터 순서대로 명령을 수행합니다.
  • routes의 원소는 "op n"과 같은 구조로 이루어져 있으며, op는 이동할 방향, n은 이동할 칸의 수를 의미합니다.
    • op는 다음 네 가지중 하나로 이루어져 있습니다.
      • N : 북쪽으로 주어진 칸만큼 이동합니다.
      • S : 남쪽으로 주어진 칸만큼 이동합니다.
      • W : 서쪽으로 주어진 칸만큼 이동합니다.
      • E : 동쪽으로 주어진 칸만큼 이동합니다.
    • 1 ≤ n ≤ 9

입출력 예

park	routes	result
["SOO","OOO","OOO"]	["E 2","S 2","W 1"]	[2,1]
["SOO","OXX","OOO"]	["E 2","S 2","W 1"]	[0,1]
["OSO","OOO","OXO","OOO"]	["E 2","S 3","W 1"]	[0,0]

알고리즘 예상

1. park 내부에 접근을 쉽게하기 위해 Array<String> 에서 List<List<Char>>의 2차원 배열형태로 바꾼다.
2. 현재 위치를 저장할 변수 X,Y를 만든다.(초기값: S위치)
3. routes의 원소를 Split과 map을 이용해 E to 2와 같이 접근이 용이하게 바꾼다.
4. 반복문과 조건문을 이용해 routes[i].first에 따라 방향을 정한다.
5. 이동 중 장애물을 만나거나 이동 후 공원을 벗어난다면 continue하고 아닐 경우에는 X, Y 값에 이동한 만큼의 값을 더한다.
6. X, Y를 answer에 더한 후 return한다.

 

초기 코드

class Solution {
    fun solution(park: Array<String>, routes: Array<String>): IntArray {
        var answer: IntArray = intArrayOf()
        return answer
    }
}

 

내 코드

// 실패
class Solution {
    fun solution(park: Array<String>, routes: Array<String>): IntArray {
        val parkList = park.map { it.map { it.toString() } }
        val routeList = routes.map { it.split(" ") }.map { it[0] to it[1].toInt() }
        val maxX = parkList[0].lastIndex
        val maxY = parkList.lastIndex
        var x: Int = parkList.filter { it.contains("S") }[0].indexOf("S")
        var y: Int = parkList.indexOfFirst { it.contains("S") }

        for (i in routeList) {
            when (i.first) {
                "E" -> {
                    if (x + i.second > maxX || parkList[x].slice(x..x + i.second)
                            .contains("X")
                    ) continue
                    else x += i.second
                }

                "W" -> {
                    if (x - i.second < 0 || parkList[x].slice(x downTo x - i.second)
                            .contains("X")
                    ) continue
                    else x -= i.second
                }

                "S" -> {
                    val checkX = parkList.map { it[x] }.slice(y..y + i.second)
                    if (y + i.second > maxY || checkX.contains("X")) continue
                    else y += i.second

                }

                "N" -> {
                    val checkX = parkList.map { it[x] }.slice(y downTo y - i.second)
                    if (y + i.second < 0 || checkX.contains("X")) continue
                    else y -= i.second
                }
            }
        }

        return intArrayOf(y, x)
    }
}

checkX를 선언할 때 slice하는 범위에서 런타임 에러가 발생했고 "N" 내부 조건문에서 y - i.second가 아닌 y+i.second인 것에서 오류가 발생했다.

// 실패
class Solution {
    fun solution(park: Array<String>, routes: Array<String>): IntArray {
        val parkList = park.map { it.map { it.toString() } }
        val routeList = routes.map { it.split(" ") }.map { it[0] to it[1].toInt() }
        val maxX = parkList[0].lastIndex
        val maxY = parkList.lastIndex
        var x: Int = parkList.filter { it.contains("S") }[0].indexOf("S")
        var y: Int = parkList.indexOfFirst { it.contains("S") }

        for (i in routeList) {
            when (i.first) {
                "E" -> {
                    if (x + i.second > maxX || parkList[x].slice(x..x + i.second)
                            .contains("X")
                    ) continue
                    else x += i.second
                }

                "W" -> {
                    if (x - i.second < 0 || parkList[x].slice(x downTo x - i.second)
                            .contains("X")
                    ) continue
                    else x -= i.second
                }

                "S" -> {
                    if (y + i.second > maxY || parkList.map { it[x] }.slice(y..y + i.second).contains("X")) continue
                    else y += i.second

                }

                "N" -> {
                    if (y - i.second < 0 || parkList.map { it[x] }.slice(y downTo y - i.second).contains("X")) continue
                    else y -= i.second
                }
            }
        }

        return intArrayOf(y, x)
    }
}

"E"와 "W"를 검사할 때 parkList[x]가 아닌 parkList[y]를 slice해야한다.

//성공
class Solution {
    fun solution(park: Array<String>, routes: Array<String>): IntArray {
        val parkList = park.map { it.map { it.toString() } }
        val routeList = routes.map { it.split(" ") }.map { it[0] to it[1].toInt() }
        val maxX = parkList[0].lastIndex
        val maxY = parkList.lastIndex
        var x: Int = parkList.filter { it.contains("S") }[0].indexOf("S")
        var y: Int = parkList.indexOfFirst { it.contains("S") }

        for (i in routeList) {
            when (i.first) {
                "E" -> {
                    if (x + i.second > maxX || parkList[y].slice(x..x + i.second).contains("X")) continue
                    else x += i.second
                }

                "W" -> {
                    if (x - i.second < 0 || parkList[y].slice(x downTo x - i.second).contains("X")) continue
                    else x -= i.second
                }

                "S" -> {
                    if (y + i.second > maxY || parkList.map { it[x] }.slice(y..y + i.second).contains("X")) continue
                    else y += i.second

                }

                "N" -> {
                    if (y - i.second < 0 || parkList.map { it[x] }.slice(y downTo y - i.second).contains("X")) continue
                    else y -= i.second
                }
            }
        }

        return intArrayOf(y, x)
    }
}

다른 사람의 풀이

class Solution {
    private fun findStart(park: Array<String>): MutableList<Int> {
        for (i in park.indices)
            for (j in park[i].indices)
                if (park[i][j] == 'S')
                    return mutableListOf(i, j)
        return mutableListOf(0, 0)
    }

    fun solution(park: Array<String>, routes: Array<String>): IntArray {
        val directions = mapOf('E' to (0 to 1), 'W' to (0 to -1), 'N' to (-1 to 0), 'S' to (1 to 0))
        return routes.map { it[0] to it.drop(2).toInt() }
                .fold(findStart(park)) { pos, (direction, distance) ->
                    val prevPos = pos.toMutableList()
                    val nextPos = pos.toMutableList()
                    repeat(distance) {
                        nextPos[0] += directions[direction]!!.first
                        nextPos[1] += directions[direction]!!.second
                        if (!(0 <= nextPos[0] && nextPos[0] < park.size && 0 <= nextPos[1] && nextPos[1] < park[0].length && park[nextPos[0]][nextPos[1]] != 'X')) 
                            return@fold prevPos
                    }
                    return@fold nextPos
                }.toIntArray()
    }
}

이 풀이는 폴드를 이용해 풀었다

개선점 또는 배운점

1. 풀이가 크게 두종류로 나뉘었는데 위 풀이처럼 direction을 정해서 구현하거나 when문을 이용해서 n만큼 이동하는 로직을 구현하였다
2. direction을 이용하는 풀이에 대해 좀 더 공부해봐야겠다.