1️⃣ 문제

문제 - 빛의 경로 사이클

풀이참조 - Blog

문제 설명

각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다.

  • 빛이 “S”가 써진 칸에 도달한 경우, 직진합니다.
  • 빛이 “L”이 써진 칸에 도달한 경우, 좌회전을 합니다.
  • 빛이 “R”이 써진 칸에 도달한 경우, 우회전을 합니다.
  • 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다.

당신은 이 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 각 사이클의 길이가 얼마인지 알고 싶습니다. 경로 사이클이란, 빛이 이동하는 순환 경로를 의미합니다.

예를 들어, 다음 그림은 격자 ["SL","LR"]에서 1행 1열에서 2행 1열 방향으로 빛을 쏠 경우, 해당 빛이 이동하는 경로 사이클을 표현한 것입니다.

ex1.png

이 격자에는 길이가 16인 사이클 1개가 있으며, 다른 사이클은 존재하지 않습니다.

격자의 정보를 나타내는 1차원 문자열 배열 grid가 매개변수로 주어집니다. 주어진 격자를 통해 만들어지는 빛의 경로 사이클의 모든 길이들을 배열에 담아 오름차순으로 정렬하여 return 하도록 solution 함수를 완성해주세요.

제한사항

  • 1 ≤

    grid

    의 길이 ≤ 500

    • 1 ≤ grid의 각 문자열의 길이 ≤ 500
    • grid의 모든 문자열의 길이는 서로 같습니다.
    • grid의 모든 문자열은 'L', 'R', 'S'로 이루어져 있습니다.
입출력 예
grid result
["SL","LR"] [16]
["S"] [1,1,1,1]
["R","R"] [4,4]
입출력 예 설명

입출력 예 #1

  • 문제 예시와 같습니다.
  • 길이가 16인 사이클이 하나 존재하므로(다른 사이클은 없습니다.), [16]을 return 해야 합니다.

입출력 예 #2

  • 주어진 격자를 통해 만들 수 있는 사이클들은 다음 그림과 같습니다.

ex2.png

  • 4개의 사이클의 길이가 모두 1이므로, [1,1,1,1]을 return 해야 합니다.

입출력 예 #3

  • 주어진 격자를 통해 만들 수 있는 사이클들은 다음 그림과 같습니다.

ex3.png

  • 2개의 사이클의 길이가 모두 4이므로, [4,4]를 return 해야 합니다.

2️⃣ 풀이 방법 및 코드

1️⃣ 처음 풀이한 코드

사실 예전에 이 문제를 시도한 적이 있었는데, 넘 어려워보여서 보류했었다 ㅎㅎ

최근에 이 문제와 비슷한 문제를 코테에선 풀고는 자신감이 생겨서 도전했지만,

공개된 테케만 맞고 히든 테케는 다 틀렸다… 코테에 제출한 문제도 그랬으려나…? ( ꈨຶ ˙̫̮ ꈨຶ )

무튼 이 문제에서 사이클, 즉 순환되는 경로는 들어왔던 방향으로 또 들어온다면 탐색을 정지하고 사이클의 길이를 리턴한다.

  • D: 방향에 따라 (x,y)에 더해야 할 값을 담은 딕셔너리
  • Dir: 빛의 방향 정보를 담는 enum
    • straight: 현재 진행 방향에서 직진할 때 변경될 방향 return
    • turnLeft: 현재 진행 방향에서 좌회전할 때 변경될 방향 return
    • turnRight: 현재 진행 방향에서 우회전할 때 변경될 방향 return
  • next(): 현재 위치 및 방향 정보와, 격자의 원소에 따라 빛이 이동해야 할 (x, y) 위치와 변경할 방향 정보를 튜플로 return하는 함수
  • visited: [[[String: Bool]]]: 2차원 격자의(grid2D)의 원소에 4방향별 방문 여부를 담은 딕셔너리를 원소로 가지는 2차원 배열
import Foundation

// 동서남북 dir
let D: [Dir: [Int]] = [.right: [0,1], .left: [0, -1], .down: [1, 0], .up: [-1, 0]]

// 빛의 방향 정보를 담는 enum
enum Dir: String {
    case right
    case left
    case up
    case down
    
    var straight: Dir {
        switch self {
            case .right:
            return .right
            case .left:
            return .left
            case .up:
            return .up
            case .down:
            return .down
        }
    }
    
    var turnLeft: Dir {
        switch self {
            case .right:
            return .up
            case .left:
            return .down
            case .up:
            return .left
            case .down:
            return .right
        }
    }
    
    var turnRight: Dir {
        switch self {
            case .right:
            return .down
            case .left:
            return .up
            case .up:
            return .right
            case .down:
            return .left
        }
    }
}

func next(_ curr: (x: Int, y: Int, d: Dir), _ g: String) -> (Int, Int, Dir) {
    var dir: Dir = curr.d
    switch g {
        case "S":
        dir = curr.d.straight
        
        case "L":
        dir = curr.d.turnLeft
        
        default: 
        dir = curr.d.turnRight
    }
    return (curr.x + D[dir]![0], curr.y + D[dir]![1], dir)
}


func solution(_ grid:[String]) -> [Int] {
    var grid2D = grid.map { $0.map { String($0) } }
    let N = grid2D.count
    let M = grid2D[0].count
    var visited = Array(repeating: Array(repeating: ["right": false, "left": false, "up": false, "down": false], count: M), count: N)
    var answer = [Int]()
    
    let dirs: [Dir] = [.right, .left, .up, .down]
    for d in dirs {
        var currD = d
        var (x, y) = (0, 0)
        var count = 0
        
        while true {
            if visited[x][y][currD.rawValue]! {
                answer += [count]
                break
            }
            visited[x][y][currD.rawValue]! = true
            
            let (nx, ny, nd) = next((x: x, y: y, d: currD), grid2D[x][y])
            
            if 0..<N ~= nx && 0..<M ~= ny {
                x = nx
                y = ny
            } else {
                if nx >= N { x = 0 }
                if nx < 0 { x = N - 1 }
                if ny >= M { y = 0 }
                if ny < 0 { y = M - 1 }
            }
            currD = nd
            count += 1
        }
    }
    return answer.filter { $0 != 0 }.sorted()
}

2️⃣ 최종 수정 코드

다른 블로그 풀이를 참조하여 아래와 같이 수정해주었다.

위 코드 대비 변경 부분

  1. 모든 grid 원소에 대해 시작 위치를 설정하여 사이클 탐색

    무조건 0행 0열에서 빛이 시작해야한다고 착각했다. 가능한 모든 사이클을 찾으려면 2중 for문으로 모든 격자에 접근해야 하고, 시작하는 방향을 4방향으로 다 시도해야 하므로, 3중 for문으로 사이클을 탐색해야 한다.

  2. 시작점을 바꿔 탐색할 때마다 초기화를 하지 않는 visited

    사이클은 순환되므로, 1-2-3-4와 5-1-2-3-4는 같은 사이클이라 초기화 해주지 않고 탐색한다.

  3. 다음으로 이동할 x, y 초기화

    조건문이 아닌 삼항 연산자로, 0 아래로 범위가 벗어나면 각 행 또는 열의 count -1로 초기화, 그게 아니라면, newValue % N 요로코럼 나머지 연산자로 배열 범위를 벗어나지 않는 값으로 초기화해준다.

import Foundation

// 동서남북 dir
let D: [Dir: [Int]] = [.right: [0,1], .left: [0, -1], .down: [1, 0], .up: [-1, 0]]

// 빛의 방향 정보를 담는 enum
enum Dir: String {
    case right
    case left
    case up
    case down
    
    var straight: Dir {
        switch self {
            case .right:
            return .right
            case .left:
            return .left
            case .up:
            return .up
            case .down:
            return .down
        }
    }
    
    var turnLeft: Dir {
        switch self {
            case .right:
            return .up
            case .left:
            return .down
            case .up:
            return .left
            case .down:
            return .right
        }
    }
    
    var turnRight: Dir {
        switch self {
            case .right:
            return .down
            case .left:
            return .up
            case .up:
            return .right
            case .down:
            return .left
        }
    }
}

// 빛이 다음으로 가야 할 위치와 방향 정보를 리턴하는 함수
func next(_ curr: (x: Int, y: Int, d: Dir), _ g: String) -> (Int, Int, Dir) {
    var dir: Dir = curr.d
    switch g {
        case "S":
        dir = curr.d.straight
        
        case "L":
        dir = curr.d.turnLeft
        
        default: 
        dir = curr.d.turnRight
    }
    return (curr.x + D[dir]![0], curr.y + D[dir]![1], dir)
}

func solution(_ grid:[String]) -> [Int] {
    let grid2D = grid.map { $0.map { String($0) } }
    let N = grid2D.count
    let M = grid2D[0].count
    var visited = Array(repeating: Array(repeating: ["right": false, "left": false, "up": false, "down": false], count: M), count: N)
    var answer = [Int]()
    
    for r in 0..<N {
        for c in 0..<M {
            for d in D.keys {
                var currD = d
                var (x, y) = (r, c)
                var count = 0
                
                 while true {
                     guard !visited[x][y][currD.rawValue]! else {
                         answer += [count]
                         break
                     }
                     visited[x][y][currD.rawValue]! = true
                     
                     let (nx, ny, nd) = next((x: x, y: y, d: currD), grid2D[x][y])
                     
                     x = nx < 0 ? N - 1: nx % N
                     y = ny < 0 ? M - 1: ny % M
                     currD = nd
                     count += 1
                 }
            }
        }
    }
    return answer.filter { $0 != 0 }.sorted()
}

3️⃣ 이 문제를 풀면서 되새긴 점

2차원 배열에서 순환 사이클을 찾을 때

단순히 2차원 배열의 원소에 접근 여부만 확인하는 것이 아니라,

해당 위치의 원소에, 현재 방향으로 들어왔는지를 확인해야 한다.

들어왔던 방향으로 또 들어온 것이라면 그것은 순환 사이클!