[알고리즘 풀이 분석] 프로그래머스 빛의 경로 사이클

nnnyeong·2022년 6월 14일
0

알고리즘 풀이분석

목록 보기
100/101

오랜만에 조금 난이도 있는 문제를 만나 기록해본다. 프로그래머스 빛의 경로 사이클




프로그래머스 빛의 경로 사이클

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

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

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

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

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

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

[제한사항]

  • 1 ≤ grid의 길이 ≤ 500
  • 1 ≤ grid의 각 문자열의 길이 ≤ 500
  • grid의 모든 문자열의 길이는 서로 같습니다.
  • grid의 모든 문자열은 'L', 'R', 'S'로 이루어져 있습니다.



입출력

gridresult
["SL","LR"][16]
["S"][1,1,1,1]
["R","R"][4,4]



풀이

레벨 2 치고는 난이도가 꽤 있는 편인 것 같다. 아무리 봐도 레벨 2는 아닌 것 같다.

특별한 알고리즘을 필요로 하진 않지만 다양한 조건과 여러 변수들을 깔끔히 다루면서 정확히 문제를 풀어내는 능력을 테스트하는 문제인 것 같다.

사실 무한히 빛이 도는 경우가 생기면 어떡하나 싶은게 가장 고민스러웠고 어려웠는데 질문 사항중에 누가 써놓은 글을 통해 힌트를 얻었다.

문제에서 '모든 경로의 사이클을 구하라' 고 한 것은 즉, '어디서 쏘아도 왔던 위치로 되돌아 온다는 것'을 의미한다는 것이다. 그렇지 않으면 문제를 풀 수 없기 때문이다. 이 사실을 캐치하는 것이 관건인 것 같다.

입력으로 주어지는 grid 를 바탕으로 각 지점에서 4가지 방향으로 빛이 뻗어 나간 경우가 있는지를 확인할 수 있도록 하고 이미 뻗어나간 적이 있다면 그 시점부터는 굳이 탐색을 계속할 필요가 없기 때문에 중단한다.

빛의 이동 방향을 4가지 방향으로 구분하고 각 방향에 따른 위치 변화량을 미리 계산 해 두었다.

또한 각 지점에 쓰여있는 "S, "L", "R" 에 따라 방향 변화를 계산해 반환하는 함수turn 을 작성해 각 지점마다의 방향 변화를 계산, 변화된 방향을 바탕으로 위치를 변화시킨다. 변화시킨 위치가 범위를 넘어갈 경우에는 순환할 수 있도록 처리한다.

처음 빛을 쏘았던 시점에 도달했을 때 사이클 길이를 저장하고 탐색을 중단하며 탐색은 모든 지점에서 모든 방향으로 이루어지도록 반복한다.

❗️ 기억할 것
입력된 grid 의 각 문자를 접글할 때 String subscript 작성을 따로 하지 않아도 되도록 map 을 이용한 점을 기억하자!!




코드

import Foundation

struct Location : Equatable {
    var y : Int, x : Int, dir : Int
}

func turn(_ to : String, _ d : Int) -> Int {
    if to == "S" {
        return d
    } else if to == "L" {
        return (d+3) % 4
    } else {
        return (d+1) % 4
    }
}

func solution(_ grid:[String]) -> [Int] {
    var answer : [Int] = []
    
    let R = grid.count
    let C = grid[0].count
    let map = grid.map{$0.map{String($0)}}
    let dy = [-1,0,1,0]
    let dx = [0,1,0,-1]
    var visited = Array(repeating: Array(repeating: Array(repeating: false, count: 4), count: C), count: R)
    
    for i in 0..<R {
        for j in 0..<C {
            for k in 0..<4 {
                if visited[i][j][k] { continue }
                
                let start = Location(y: i, x: j, dir: k)
                var cur = start
                var count = 0
                
                while (true){
                    if visited[cur.y][cur.x][cur.dir] { break }
                    
                    count += 1
                    visited[cur.y][cur.x][cur.dir] = true
                    
                    let nd = turn(map[cur.y][cur.x], cur.dir)
                    let ny = (cur.y + dy[nd] + R) % R
                    let nx = (cur.x + dx[nd] + C) % C
                    
                    cur.y = ny
                    cur.x = nx
                    cur.dir = nd
                    
                    if cur == start && count > 0 {
                        answer.append(count)
                        break
                    }
                }
                
            }
        }
    }
    
    return answer.sorted()
}
profile
주니어 개발자까지 ☄️☄️

0개의 댓글