[프로그래머스 Lv.2] 방문길이 풀이 및 해설 feat. Swift

안녕하세요:)

레인스톤입니다.

 

오늘은 프로그래머스 Lv.2 방문길이 문제

swift 풀이를 살펴보겠습니다.

 

문제 설명

게임 캐릭터를 4가지 명령어를 통해 움직이려고 합니다.

 

1. U: 위쪽으로 한 칸 가기
2. D: 아래쪽으로 한 칸 가기
3. R: 오른쪽으로 한 칸 가기
4. L: 왼쪽으로 한 칸 가기

캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다.

좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5),

오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다.

 

이 때 게임 캐릭터가 명령어를 통해 지나간 길 중 캐릭터가 처음 간 길의 길이를 구하려고 합니다.

명령어가 매개변수 dirs로 주어질 때, 게임 캐릭터가 처음 걸어본 길의 길이를 구하여 return하는 solution함수를 완성해주세요.

 

문제 링크

 

제한사항

1. dirs는 string형으로 주어지며 'U', 'D', 'R', 'L' 이외에 문자는 주어지지 않습니다.
2. dirs의 길이는 500이하의 자연수입니다.

 

제한 사항 분석

1. dirs가 명확하게 주어져서 switch문으로 해결 가능
2. 500이하의 자연수이기 때문에 시간 복잡도의 중요도가 낮음
3. 자연수이기 때문에 empty 경우는 배제(교육 과정상 자연수에는 0은 미포함)

 

풀이 기획

난이도가 높지 않은 문제에서는항상 문제에서 시키는대로 구현하는 연습을 해야합니다.

 

1. (0, 0)에서 시작합니다.
2. dirs를 탐색하면서 방향에 따라 어디로 이동할지 정합니다.
3. U는 한 칸 위, D는 한 칸 아래, L은 왼쪽으로 한 칸, R은 오른쪽으로 한 칸입니다.
4. 이동할 위치가 좌표평면 범위 내에 있는지 확인해줍니다.
   1. 범위내에 있지 않다면 해당 명령어는 무시하고 다음 명령어를 탐색합니다.
5. 이동할 위치가 범위내에 있다면 이미 걸어본 길인지 확인합니다.
   1. 걸어본 길이라면 현재 위치를 업데이트하고 다음 명령어를 탐색합니다.
6. 걸어본 길이 아니라면 방문 체크를 하고 현재 위치를 업데이트하고 다음 명령어를 탐색합니다.
7. 방문 체크된 위치의 수(count)를 return합니다.

 

풀이 과정

var now = [0, 0]
var visited: Set<[Int]> = []

시작 위치는 (0, 0)에서 시작합니다.

한 번 걸어본 길을 체크하기 위해 visited 변수를 생성합니다.

이 때 Set을 활용한 이유는 중복을 제거하기 위함과 배열과 다르게

contains의 시간 복잡도가 상수 시간복잡도이기 때문입니다.

참고로 Set은 해쉬 테이블 자료구조 입니다.

 

for dir in dirs {
    var (dx, dy) = (0, 0)
    switch dir {
    case "U": (dx, dy) = (0, 1)
    case "D": (dx, dy) = (0, -1)
    case "L": (dx, dy) = (-1, 0)
    case "R": (dx, dy) = (1, 0)
    default: break
    }
}

명령어를 for-loop를 통해 탐색해줍니다.

이 때 dx, dy는 어느 방향으로 얼마나 이동할지를 나타냅니다.

U는 한 칸 위기 때문에 dy값만 1로 바꿔줍니다.

D는 한 칸 아래이기 때문에 dy값만 -1로 바꿔줍니다.

L은 한 칸 왼쪽이기 때문에 dx값만 -1로 바꿔줍니다.

R은 한 칸 오른쪽이기 때문에 dx값만 1로 바꿔줍니다.

 

let next = [now[0]+dx, now[1]+dy]
if abs(next[0]) > 5 || abs(next[1]) > 5 { continue }

현재 위치에 dx, dy값을 더해 다음(이동할) 위치를 구해줍니다.

해당 위치가 좌표평면 범위 내에 있는지 확인해줍니다.

범위 내에 있지 않다면 continue를 통해 다음 명령어를 탐색합니다.

절대값을 통해 비교하면 -5 ~ 5 사이에 있는지 확인하지 않아도 됩니다.

예를 들어 -6의 경우 절대값을 통해 6으로 만들고 5와 비교하면 -6을 -5와 비교한 결과와 같습니다:)

 

if !visited.contains(now+next) && !visited.contains(next+now) {
    visited.insert(now+next)
}
        
now = next

이전에 걸어봤던 길인지를 visited를 통해 확인합니다.

(0, 1)에서 (0, 2)로 이동한 경우와 (0, 2)에서 (0, 1)로 이동한 경우는같은 길을 걸었다고 볼 수 있기 때문에

visited 여부를 체크할 때 (now + next), (next + now)를 모두 체크합니다.

걸어본 길이 아니라면 visited에 새로운 정보를 업데이트해줍니다.

다음 탐색을 위해 현재 위치를 이동할 위치로 업데이트 해줍니다.

 

return visited.count

반복문이 끝난 이후에는 방문한 길의 수(count)를 return합니다.

 

전체 코드

func solution(_ dirs:String) -> Int {
    var now = [0, 0]
    var visited: Set<[Int]> = []

    for dir in dirs {
        var (dx, dy) = (0, 0)

        switch dir {
        case "U": (dx, dy) = (0, 1)
        case "D": (dx, dy) = (0, -1)
        case "L": (dx, dy) = (-1, 0)
        case "R": (dx, dy) = (1, 0)
        default: break
        }

        let next = [now[0]+dx, now[1]+dy]
        if abs(next[0]) > 5 || abs(next[1]) > 5 { continue }
        
        if !visited.contains(now+next) && !visited.contains(next+now) {
            visited.insert(now+next)
        }
        
        now = next
    }
    return visited.count
}