[Algorithm] [Python] Programmers - 방문 길이

방문 길이

 

문제 설명

---

게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.

• U: 위쪽으로 한 칸 가기

• D: 아래쪽으로 한 칸 가기

• R: 오른쪽으로 한 칸 가기

• L: 왼쪽으로 한 칸 가기

캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다.

이때, 우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다. 예를 들어 위의 예시에서 게임 캐릭터가 움직인 길이는 9이지만, 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다. (8, 9번 명령어에서 움직인 길은 2, 3번 명령어에서 이미 거쳐 간 길입니다)

단, 좌표평면의 경계를 넘어가는 명령어는 무시합니다.

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

 

제한사항

---

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

 

입출력 예

---

• dirs : "ULURRDLLU", answer : 7
• dirs : "LULLLLLLU", answer : 7

 

제출 코드

---

def solution(dirs):
    X, Y = 0, 1
    src = [0, 0]
    paths = set()
    delta = {
        "U" : [0, 1],
        "D" : [0, -1],
        "L" : [-1, 0],
        "R" : [1, 0]
    }

    for dir in dirs:
        dest = [src[X] + delta[dir][X], src[Y] + delta[dir][Y]]

        if boundary_check(dest):
            pos = tuple(src + dest)
            paths.add(pos)
            pos = tuple(dest + src)
            paths.add(pos)
            src = dest
    return len(paths) // 2

def boundary_check(pos):
    X, Y = 0, 1
    if -5 <= pos[X] <= 5 and -5 <= pos[Y] <= 5:
        return True
    return False 

 

코드 설명

---

위 문제는 걸어온 길 중 처음 걸어본 길의 길이를 구해야한다. 문제의 핵심은 중복 제거 였다.

따라서, 중복하여 걸은 길의 중복을 제거하기 위해 set 자료형을 이용하였다.

상, 하, 좌, 우 움직임에 따른 변화량을 딕셔너리 타입으로 delta 변수에 정의하고 매 움직임마다의 목적지의 위치가 유효한 위치인지 체크하기 위해 boundary_check 라는 함수를 작성하여 검증하였다.

이후 dirs 를 순회하며 중복 제거를 위해 매 dir 마다 (src[X], src[Y], dest[X], dest[Y]) , (dest[X], dest[Y], src{X], src[Y])) 값을 모두 paths 변수에 더해주었다.

본 문제에서 (0,0) -> (0,1) 의 움직임은 (0,1) -> (0,0) 과 동일한 것으로 분류되기 때문에 위와 같이 (src, dest) , (dest, src) 두 값을 모두 더해주었다.

이후 최종적으로 paths 변수 길이의 반을 리턴하였다.