프로그래머스 Level 2 리코쳇 로봇

리코쳇 로봇

출처: 프로그래머스

https://school.programmers.co.kr/learn/courses/30/lessons/169199

프로그래머스

광고 게시가 없는 비상업적, 비영리적 포스트입니다.

 

혹시 아래 사진 기억하시는 분???

문제를 읽고 저는 이게 떠올랐습니다

포켓몬스터 골드버전입니다.

찾아보니 얼음샛길이라고 하네요ㅋㅋ

갑자기 왜 뜬금없이 포켓몬 골드버전인가 이번 문제가 딱 저거입니다.

 

문제 정리 

출처 프로그래머스

문제를 그림으로 표현하면 아래처럼 이동합니다.

문제가 무엇을 말하고 있는지 이해가 조금 되시나요??

 

처음 R에서는 두 곳으로 갈 수 있습니다.

 

저 길 중 하나를 선택해서 아래처럼 갈 수 있는 곳을 찾아 아래로 내려갑니다.

 

그러다가 이렇게 또 갈 수 있는 곳이 여러 개인 곳이 나오면 그중 하나로 갑니다 

 

 

이렇게 각 경우의 노드에서 갈 수 있는 경로로 들어가 최종 G에 도달하는지 알아야 합니다.

도달한다면 언제 가장 짧게 가는지 

도달하지 않는다면 -1을

 

dfs( 노드 )

if - 지금의 노드가 G이면 return

지금 노드에서 갈 수 있는 다음 노드들을 탐색하는 함수

for 탐색한 노드들

     dfs( 다음 노드 ) 

 

대략 이렇게 할 수 있겠네요.

 

bfs(노드)

큐에 노드를 삽입

while(큐가 안 비어있으면)

  if - 지금의 노드가 G면 종료

  지금 노드에서 갈 수 있는 다음 노드들을 탐색

  방문하지 않았다면 큐에 삽입

 

두 가지 중 어떤 걸 할지는 선택입니다.

 

아래에 코드가 있습니다. 

 

import java.util.LinkedList

class Solution {
    val dy = intArrayOf(-1, 0, 1, 0)
    val dx = intArrayOf(0, 1, 0, -1)

    fun solution(board: Array<String>): Int {
        val start = findStartNode(board)
        return bfs(
            board,
            Array(board.size) { BooleanArray(board[0].length) },
            intArrayOf(start.first, start.second, 0)
        )
    }

    fun bfs(
        board: Array<String>,
        visited: Array<BooleanArray>,
        node: IntArray,
    ): Int {
        val queue = LinkedList<IntArray>()
        queue.add(node)
        while (queue.isNotEmpty()) {
            val current = queue.removeFirst()
            val cRow = current[0]
            val cCol = current[1]
            val cCnt = current[2]
            if (board[cRow][cCol] == 'G') return cCnt
            for (i in 0..3) {
                val next = findNextNode(board, cRow, cCol, dy[i], dx[i])
                if (next != Pair(cRow, cCol) && !visited[next.first][next.second]) {
                    queue.add(intArrayOf(next.first, next.second, current[2] + 1))
                    visited[next.first][next.second] = true
                }
            }
        }
        return -1
    }
    
    fun dfs(
        board: Array<String>,
        visited: Array<BooleanArray>,
        cntArr: Array<IntArray>,
        start: Pair<Int, Int>,
        cnt: Int,
        minCnt: Int,
    ): Int {
        var m = minCnt
        if (board[start.first][start.second] == 'G') return min(m, cnt)
        for (i in 0..3) {
            val next = findNextNode(board, start.first, start.second, dy[i], dx[i])
            val nextRow = next.first
            val nextCol = next.second
            if (next != start && !visited[nextRow][nextCol] && cnt + 1 < cntArr[nextRow][nextCol]) {
                visited[nextRow][nextCol] = true
                cntArr[nextRow][nextCol] = cnt + 1
                m = dfs(board, visited, cntArr, next, cnt + 1, m)
                visited[nextRow][nextCol] = false
            }
        }
        return m
    }


    fun findNextNode(board: Array<String>, startRow: Int, startCol: Int, dy: Int, dx: Int): Pair<Int, Int> {
        var row = startRow
        var column = startCol
        while (true) {
            if (row + dy == -1 || row + dy == board.size) return Pair(row, column)
            if (column + dx == -1 || column + dx == board[0].length) return Pair(row, column)
            if (board[row + dy][column + dx] == 'D') return Pair(row, column)
            row += dy
            column += dx
        }
    }

    fun findStartNode(board: Array<String>): Pair<Int, Int> {
        var start = Pair(0, 0)
        board.forEachIndexed { row, s ->
            s.forEachIndexed { column, c ->
                if (c == 'R') start = Pair(row, column)
            }
        }
        return start
    }
}

 

풀이 그대로 하지 마시고 왜 이렇게 했는지 하나씩 살펴보신 후에 참고하시면서

본인의 스타일대로 작성하시면 됩니다. 복붙 하면 실력은 안 늘고 손해니까요

이상입니다. 감사합니다.