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

 

Problem

 

코딩테스트 연습 - 빛의 경로 사이클

---

Solution

 

1. 사이클에 대한 개념을 이해한다.

 

사이클은 처음 시작한 칸에서 처음 시작한 방향으로 다시 되돌아 올 때 사이클이 형성됩니다.

 

즉 (0,0)에서 오른쪽으로 빛을 쐈고 다시 (0,0)에서 오른쪽으로 들어오는 빛이 있다면 사이클입니다.

 

2. 위치와 방향을 기억할 Location 구조체를 만들어준다.

 

struct Location:Equatable {
    var x:Int,y:Int,d:String
}

 

3. 사이클을 구하는데 필요한 값들을 미리 정의해놓는다.

 

dValue: 방향에 따라 위치가 바뀌어야할 값

 

next: 진행된 방향이 우회전 좌회전 직진에 따라 바뀔 방향

 

answer: 사이클의 길이들

 

g: grid의 이중 배열

 

visited: 각 칸의 방향별 방문이력을 저장

 

let dValue = ["up":(0,-1),"down":(0,1),"left":(-1,0),"right":(1,0)]
let next:[String:[String:String]] = ["L":["down":"right","right":"up","up":"left","left":"down"],"R":["down":"left","right":"down","up":"right","left":"up"],"S":["down":"down","right":"right","up":"up","left":"left"]]
var answer:[Int] = []
let g = grid.map{$0.map{String($0)}}
var visited = Array(repeating: Array(repeating:["up":false,"down":false,"right":false,"left":false], count: g[0].count), count: g.count)

 

4. 모든 칸에서 모든 방향에 따라 사이클을 만드는지 확인한다.

 

3중 포문 모든 x,y에서의 위,아래,오른쪽,왼쪽으로 확인합니다.

 

만약 이미 방문했다면 break를 하고 그게 아니라면 다음 위치로 넘어가도록 합니다.

 

그러다가 맨 처음 시작된 위치가 되돌아왔다면 count를 answer에 넣어줍니다.

 

 for y in 0..<g.count {
        for x in 0..<g[0].count {
            for d in dValue.keys {
                let first = Location(x: x, y: y, d: d)
                var location:Location = first
                var count:Int = 0
                while true {
                    if visited[location.y][location.x][location.d]! { break }
                    visited[location.y][location.x][location.d] = true
                    count += 1
                    let direction = g[location.y][location.x]
                    location.d = next[direction]![location.d]!
                    location.x += dValue[location.d]!.0
                    location.y += dValue[location.d]!.1
                    location.x = location.x < 0 ? g[0].count-1 : location.x%g[0].count
                    location.y = location.y < 0 ? g.count-1 : location.y%g.count
                    if location == first && count != 0{
                        answer.append(count)
                        break
                    }
                }
            }
        }
    }

 

5. answer를 오름차순으로 정렬해 반환한다.

 

return answer.sorted()

---

Source Code

 

---

P.S

 

이건 2단계라고 보기엔 어려울 것 같다.... 3단계에서도 조금 난이도 있는 문제같은데...

 

처음에 사이클에 대한 개념을 이해할 때 1 - 2 - 3 - 4 와 5 - 1 - 2 - 3 - 4 는 다른 사이클이라고 생각하고

 

방문이력을 빛이 처음 시작할 때마다 초기화해줬는데.. 그게 아니였다... 그것만 바로 알았더라도 빨리 풀었을텐데..

 

Swift로는 2번째로 문제를 푼 사람이여서  뿌듯했다...ㅎㅎ