[프로그래머스] 월간 코드 챌린지 시즌3 빛의 경로 사이클 with Swift

안녕하세요. 오늘은 프로그래머스 빛의 경로 사이클 문제를 풀어보겠습니다!

빛의 경로 사이클 문제는 각각의 포인트에 대하여 모든 방향으로 지나갔는지 안 지나갔는지 확인하면서 경로의 길이를 측정하면 되는 문제입니다!

 

문제를 위와 같이 간소화 할 수 있는 이유는 지나간 길은 다시 돌아와 지나가기 때문에 같은 사이클이기 때문입니다.

 

그러기 위해서 isVisited와 Map을 만들어줍니다!

x = grid[0].count
y = grid.count
for i in 0..<y {
    isVisited.append([])
    map.append([])
    for j in 0..<x {
        let character = grid[i][grid[i].index(grid[i].startIndex, offsetBy: j)]
        if character == "S" {
            map[i].append(0)
        }
        else if character == "L" {
            map[i].append(1)
        }
        else if character == "R" {
            map[i].append(2)
        }
        isVisited[i].append([0,0,0,0])
    }
}

 

이후 모든 방향에 대해서 탐색을 해주시면서 length가 0이 아닐 때 정답 배열에 append해주시면 되겠습니다!

for i in 0..<y {
    for j in 0..<x {
        for k in 0..<4 {
            let length = tour(j,i,k)
            if length != 0 {
                answer.append(length)
            }
        }
    }
}

 

탐색은 재귀함수로 해줄 건데 탐색하여 isVisited가 0이 아닐 때까지 해주면 사이클이 완성되므로 탈출 조건에 isVisited를 0으로 만들어주고 다음 방향을 정하여 재귀하면 됩니다!

func tour(_ startX:Int, _ startY:Int, _ startDirection:Int) -> Int {
    if isVisited[startY][startX][startDirection] != 0 {
        return 0
    }
    isVisited[startY][startX][startDirection] = 1
    
    let nextDirection = reflect[map[startY][startX]][startDirection]
    var nextX = startX + direction[nextDirection][1]
    var nextY = startY + direction[nextDirection][0]
    
    nextX = next(nextX, x)
    nextY = next(nextY, y)
    return 1 + tour(nextX, nextY, nextDirection)
}

 

 

---

import Foundation

var isVisited:[[[Int]]] = [[[Int]]]()
var map:[[Int]] = [[Int]]() // [y][x]
                          // >        v      <        ^
let direction:[[Int]] = [[ 0, 1],[ 1, 0],[ 0,-1],[-1, 0]]

let reflect:[[Int]] = [[0,1,2,3], // S
                       [3,0,1,2], // L
                       [1,2,3,0]] // R
var x = 0
var y = 0
func next(_ data: Int, _ wall: Int) -> Int {
    var data = data
    data = data > wall - 1 ? 0 : data
    data = data < 0 ? wall - 1 : data
    return data
}

func tour(_ startX:Int, _ startY:Int, _ startDirection:Int) -> Int {
    if isVisited[startY][startX][startDirection] != 0 {
        return 0
    }
    isVisited[startY][startX][startDirection] = 1
    
    let nextDirection = reflect[map[startY][startX]][startDirection]
    var nextX = startX + direction[nextDirection][1]
    var nextY = startY + direction[nextDirection][0]
    
    nextX = next(nextX, x)
    nextY = next(nextY, y)
    return 1 + tour(nextX, nextY, nextDirection)
}

func solution(_ grid:[String]) -> [Int] {
    var answer:[Int] = [Int]()
    x = grid[0].count
    y = grid.count
    for i in 0..<y {
        isVisited.append([])
        map.append([])
        for j in 0..<x {
            let character = grid[i][grid[i].index(grid[i].startIndex, offsetBy: j)]
            if character == "S" {
                map[i].append(0)
            }
            else if character == "L" {
                map[i].append(1)
            }
            else if character == "R" {
                map[i].append(2)
            }
            isVisited[i].append([0,0,0,0])
        }
    }
    
    for i in 0..<y {
        for j in 0..<x {
            for k in 0..<4 {
                let length = tour(j,i,k)
                if length != 0 {
                    answer.append(length)
                }
            }
        }
    }
    
    return answer.sorted()
}

 

오늘은 여기까지이며 질문이 있으시면 댓글로 남겨주세요~

 

좋은 하루 보내세요!