[프로그래머스] 방문 길이

https://programmers.co.kr/learn/courses/30/lessons/49994?language=swift# 

코딩테스트 연습 - 방문 길이

 

5x5 그리드 내 (0,0)에 캐릭터가 서있고, 방향이 주어졌을 때 실제로 이동이 가능해야하고, 중복되지 않는 경로만을 거친다고 했을 때 이동한 총 거리를 구해주면된다! 

 

여기서 포인트는 양방향이 가능하기에 이 두 가지를 고려해줘야 한다는 것이다

 

A > B 와 B > A는 같다!!

 

정리해보면 중요한 조건은 두 가지이다. 

 

1. 그리드 밖을 벗어나는 이동은 skip한다.

2. 이미 지나간 경로를 세주지 않는다. 

 

 

문제의 예를 봐보자. 

 

전체 이동 명령어

1 ~ 7 이동

1부터 7까지는 중복 및 그리드를 벗어나지 않고 잘 이동할 수 있다. 

8~9 이동

하지만 8,9는 기존 경로와 겹치기 때문에, 이런 경우 8,9의 경로는 세주지 않게 되는 것이다. 

그리드를 벗어나는 건 쉬우니 따로 예로 보지 않겠다!

 

import Foundation

func solution(_ dirs:String) -> Int {
    // 현위치
    var cur = [0,0]
    // 경로를 저장 
    var paths = [[Int]:[[Int]]]()
    // 총 이동 거리
    var count = 0
    
    // 방향
    for dir in dirs { 
        // 다음 이동 경로를 우선 현위치를 기준으로 설정한다. 
        var next = cur
        
        // 방향에 따른 next 값 변경
        switch dir {            
        case "U":
            next[1] += 1
        case "D":
            next[1] -= 1
        case "L":
            next[0] -= 1
        case "R":
            next[0] += 1
        default:
            break
        }   
        // 그리드를 벗어나지 않도록 해준다. 
        if abs(next[0]) < 6 && abs(next[1]) < 6 {
            // 현위치를 기준으로 한 경로가 있다면
            if let val = paths[cur] {
                // 지나치지 않은 경로여야 함
                if !val.contains(next) {
                    // 새로 추가!
                    paths[cur]!.append(next)
                    // 양방향으로 고려해줘야함
                    if let v = paths[next] {
                        paths[next]!.append(cur)
                    } else {
                        paths[next] = [cur]
                    }
                    count += 1
                }
            // 현위치 기준 경로가 없다면    
            } else {
                // 양방향 추가!
                paths[cur] = [next]
                paths[next] = [cur]
                count += 1
            }
            // 현위치 이동!
            cur = next
        }
    }
    
    return count
}

 

두 개의 조건을 고려하면서 구현한다면 크게 어렵지 않은 문제!

 

끄읕