[Swift/프로그래머스] 리코쳇 로봇 (BFS)

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

프로그래머스

 

N-Queen 문제처럼 끝까지 dx dy 좌표 이동을 끝까지 한뒤에 걸리는 게 있는 지 없는 지 판별을 하는 방식으로 구현하는 문제였다.

 

import Foundation

func solution(_ board:[String]) -> Int {
    let dx = [-1,0,1,0]
    let dy = [0,1,0,-1]
    
    // 큐에 이동 횟수도 함께 저장
    var queue = [(x: Int, y: Int, count: Int)]()
    var visited = Set<String>()
    var map = [[Character]](repeating: [], count : board.count)
    
    for (index , i) in board.enumerated() {
        let arr = Array(i)
        map[index] = arr
    }
    
    let maxY = board[0].count - 1
    let maxX = board.count - 1
    
    var start : (Int,Int) = (0,0)
    var end : (Int,Int) = (0,0)
    
    for i in 0...maxX {
        for j in 0...maxY {
            if map[i][j] == "R" {
                start = (i,j)
            }
            if map[i][j] == "G" {
                end = (i,j)
            }
        }
    }
    
    // 시작점에서의 이동 횟수는 0
    queue.append((x: start.0, y: start.1, count: 0))
    visited.insert("x\(start.0)y\(start.1)")
    
    while !queue.isEmpty {
        let point = queue.removeFirst()
        let x = point.x
        let y = point.y
        let count = point.count
        
        for i in 0...3 {
            var r = x
            var c = y
            
            while true {
                let nr = r + dx[i]
                let nc = c + dy[i]
                
                if nr < 0 || nr > maxX || nc < 0 || nc > maxY || map[nr][nc] == "D" {
                    if (r,c) == end {
                        return count+1  // 현재까지의 이동 횟수 반환
                    }
                    
                    if !visited.contains("x\(r)y\(c)") {
                        visited.insert("x\(r)y\(c)")
                        queue.append((x: r, y: c, count: count + 1))  // 이동 횟수 증가
                    }
                    break
                }
                r = nr
                c = nc
            }
        }
    }
    
    return -1
}