프로그래머스 리코쳇 로봇 swift

문제설명

리코쳇 로봇이라는 보드게임이 있습니다.

이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다.

이 게임에서 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다.다음은 보드게임판을 나타낸 예시입니다.

...D..R
.D.G...
....D.D
D....D.
..D....

여기서 "."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.
위 예시에서는 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 "G" 위치에 멈춰 설 수 있으며, 이것이 최소 움직임 중 하나입니다.

게임판의 상태를 나타내는 문자열 배열 board가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return 하는 solution함수를 완성하세요. 만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.

 

 

제한사항

• 3 ≤ board의 길이 ≤ 100
  • 3 ≤ board의 원소의 길이 ≤ 100
  • board의 원소의 길이는 모두 동일합니다.
  • 문자열은 ".", "D", "R", "G"로만 구성되어 있으며 각각 빈 공간, 장애물, 로봇의 처음 위치, 목표 지점을 나타냅니다.
  • "R"과 "G"는 한 번씩 등장합니다.

 

풀이

저는 bfs로 풀었습니다.

아이디어

- 시작지점에서 보드판 위에 도달이 가능한 위치는 정해져 있습니다.(아무런 장애물도 없고 보드의 끝도 아닌 곳에서 멈춰설 수는 없으니까요)

- 각 위치에 도달하기까지 bfs로 최단거리를 구해보자!!

1. 시작지점과 골인지점을 찾습니다. 시작지점 찾을 때 찾는 김에 Queue에 넣었습니다

2. 장애물을 만나거나 보드판의 끝에 도달할 때까지 (아래, 위, 오른쪽, 왼쪽) 방향으로  쭉쭉 확인하며 나아갑니다.

3. 도달한 위치에 해당하는 visited배열의 값과 현재 내 이동횟수의 값을 비교해서 현재 내 이동횟수가 작으면 visited를 업데이트 해주고 Queue에 도달한 위치를 넣습니다

4. 큐가 빌 때까지 반복합니다

5. 골인지점의 값을 반환합니다.

 

func solution(_ board: [String]) -> Int {
    var visited = Array(repeating: Array(repeating: Int.max, count: board[0].count), count: board.count)
    var queue = [[Int]]()
    var goalI = 0
    var goalJ = 0

    for i in 0 ..< board.count {
        for j in 0 ..< board[0].count {
            let row = Array(board[i])
            if row[j] == "R" {
                queue.append([i,j])
                visited[i][j] = 0
            } else if row[j] == "G" {
                goalI = i
                goalJ = j
            }
        }
    }

    repeat {
        let item = queue.removeFirst()

        // 아래로 Y값을 증가시키며 가봅시다.
        var curI = item[0]
        var curJ = item[1]
        repeat {
            let row = Array(board[curI])
            if row[curJ] == "D" {
                break
            }
            curI += 1
        } while (curI < board.count)
        if visited[curI-1][curJ] > visited[item[0]][item[1]] + 1 {
            visited[curI-1][curJ] = visited[item[0]][item[1]] + 1
            queue.append([curI-1, curJ])
        }

        // 위로
        curI = item[0]
        curJ = item[1]
        repeat {
            let row = Array(board[curI])
            if row[curJ] == "D" {
                break
            }
            curI -= 1
        } while (curI >= 0)
        if visited[curI+1][curJ] > visited[item[0]][item[1]] + 1 {
            visited[curI+1][curJ] = visited[item[0]][item[1]] + 1
            queue.append([curI+1, curJ])
        }

        // 오른쪽으로
        curI = item[0]
        curJ = item[1]
        var row = Array(board[curI])
        repeat {
            if row[curJ] == "D" {
                break
            }
            curJ += 1
        } while (curJ < board[0].count)
        if visited[curI][curJ-1] > visited[item[0]][item[1]] + 1 {
            visited[curI][curJ-1] = visited[item[0]][item[1]] + 1
            queue.append([curI, curJ-1])
        }

        // 왼쪽으로
        curI = item[0]
        curJ = item[1]
        row = Array(board[curI])
        repeat {
            if row[curJ] == "D" {
                break
            }
            curJ -= 1
        } while (curJ >= 0)
        if visited[curI][curJ+1] > visited[item[0]][item[1]] + 1 {
            visited[curI][curJ+1] = visited[item[0]][item[1]] + 1
            queue.append([curI, curJ+1])
        }

    } while (!queue.isEmpty)

    return visited[goalI][goalJ] == Int.max ? -1 : visited[goalI][goalJ]
}