[프로그래머스 알고리즘] 조이스틱 문제 - A* 알고리즘은 옳습니다. 틀린 건 저에요.

알고리즘 공부 서비스 중 국내에서는 탑급에 속하는 프로그래머스의 알고리즘 문제를 최근에 재밌게 풀어서 글을 올립니다.

 

조이스틱이라는 문제로 코딩테스트 > 탐욕법(그리디) 부분에 있습니다.

• https://school.programmers.co.kr/learn/courses/30/lessons/42860

문제를 간단히 설명하면 다음과 같습니다.

 

영어 알파벳 대문자로만 이뤄진 글씨를 출력하는 프로그램이 있습니다.
프로그램은 wasd 입력만을 받으며 각각의 키는 다음 기능을 합니다.

w : 현재 커서가 위치한 알파벳을 증가시킵니다(예를 들어, A는 B로, B는 C로 변경합니다).
a : 커서의 위치를 왼쪽으로 이동시킵니다. 커서가 문자열의 첫자리에 위치할 경우 마지막 문자로 위치시킵니다.
s : 현재 커서가 위치한 알파벳을 감소시킵니다(예를 들어, B는 A로, C는 B로 변경합니다).
d : 커서의 위치를 오른쪽으로 이동시킵니다. 커서가 문자열의 마지막에 위치할 경우 첫번째 문자로 위치시킵니다.

문자열이 주어졌을 때, 최소 몇번의 키 입력으로 "AAA..."를 주어진 문자열로 바꿀 수 있을까요?
(문제가 시작될 때, 커서는 첫번째 문자에 위치합니다)

 

문제 설명을 찬찬히 읽어보니 A*로 풀 수 있을 것 같더라고요.
"경로 계획 알고리즘을 열심히 공부하고 있으니 이 정도 응용은 할 수 있어야지!" 라는 마음으로 시작했다가
몇시간은 고생했네요 ㅋㅋㅋ쿠ㅠ

 

1차 시도

A* 알고리즘을 적용할 것이니 일단 노드와 엣지를 정의해야겠죠?

 

노드는 현재 문자열입니다. 시작 노드는 "AAA..." 이고, 목표 노드는 주어진 문자열이 됩니다.

엣지는 가능한 키 입력인 w, a, s, d가 됩니다.

 

이제 남은건 f, g, h 함수들을 정의하는 것입니다.

최소한의 키 입력으로 주어진 문자열을 만들어야 하므로 중요한 요소는 키 입력 횟수입니다.

그러면 현재 상태를 알려주는 g를 다음과 같이 정의할 수 있습니다.

• g = 지금까지 키 입력한 횟수

현재 노드와 목표 노드까지의 거리를 계산하는 h는 다음과 같이 정의할 수 있습니다.

• h = 현재 문자열과 목표 문자열의 차이

 

 

노드, 엣지, f, g, h가 정의되었으니 A* 알고리즘을 구현하면 답을 구할 수 있을 것이라고 생각했지만...

키 입력 하나 하나를 엣지로 만드니 목표 노드까지 가는데 시간이 오래 걸려서 문자열이 길어지니 타임아웃이 발생하였습니다 ㅜ

 

그러면 이걸 어떻게 단축시킬 수 있을까요?

 

2차 시도

방법은 너무 간단했습니다. 현재 커서가 위치한 문자를 정답 문자열로 바로 바꾸는 것이죠.

w 혹은 s는 한번씩만 누르는 것이 아니라 목표 문자까지 바로 바꾸는 것입니다.

그러면 탐색해야 할 노드들이 a, d만으로 이어지게 되서 탐색해야 하는 노드 수가 획기적으로 줄어들게 됩니다!

 

여기까지 구현하니 모든 테스트 케이스가 통과되고 문제를 해결할 수 있었습니다.

처음에는 쉽게 해결할 줄 알았는데 중간중간 실수도 하면서 시간이 오래 걸려버렸네요 ㅜ

 

다음에도 재밌는 문제 있으면 공유하도록 하겠습니다!

 

P.S. 1

 

제출한 코드입니다.

부족한 코드지만 혹시라도 공부에 도움이 되실까 싶어서 공유드립니다.

import copy

def h(node, dest):
    result = 0
    for i in range(len(node)):
        c_n = ord(node[i])
        d_n = ord(dest[i])
        diff = abs(c_n-d_n)
        result += min(diff, (26-diff))
    return result

def calc_distance(word, name, cursor, move):
    for i in range(len(word)):
        cursor += direction
        cursor %= len(word)
        if word[cursor] != name[cursor]:
            return i+1
    return 0

def calc_left_distance(word, name, cursor):
    return calc_distance(word, name, cursor, -1)

def calc_right_distance(word, name, cursor):
    return calc_distance(word, name, cursor, 1)

def solution(name):
    queue = [{"word":["A"]*len(name), "cursor":0, "g":0, "history":""}]

    while len(queue) > 0:
        node = queue.pop(0)
        word = node["word"]
        if h(word, name) == 0:
            return node["g"]

        cur_diff = abs(ord(node["word"][node["cursor"]]) - ord(name[node["cursor"]]))
        cur_diff = min(cur_diff, 26-cur_diff)
        node["g"] += cur_diff
        node["word"][node["cursor"]] = name[node["cursor"]]
        node["history"] += f"c({cur_diff})"
        if cur_diff > 0 and h(node["word"], name) == 0:
            queue.append(copy.deepcopy(node))
        
        node_1 = copy.deepcopy(node)
        left_distance = calc_left_distance(node_1["word"], name, node_1["cursor"])
        node_1["g"] += left_distance
        node_1["cursor"] = (node_1["cursor"] - left_distance)%len(word)
        node_1["history"] += f"l({left_distance})"
        queue.append(node_1)

        node_2 = copy.deepcopy(node)
        right_distance = calc_right_distance(node_2["word"], name, node_2["cursor"])
        node_2["g"] += right_distance
        node_2["cursor"] = (node_2["cursor"] + right_distance)%len(word)
        node_2["history"] += f"r({right_distance})"
        queue.append(node_2)

        queue = sorted(queue, key=lambda x:x["g"]+h(x["word"], name))

 

P.S. 2

A* 알고리즘은 h에 따라서 성능이 달라지게 됩니다.

이 문제에서도 적용될지 궁금해서 "h = 0" 과 "h = 현재 문자열과 목표 문자열의 차이" 을 비교해봤습니다.

정말로 성능 차이가 나더라고요...!

h = 0
테스트 1 〉	통과 (0.21ms, 10.2MB)
테스트 2 〉	통과 (1.91ms, 10.3MB)
테스트 3 〉	통과 (0.19ms, 10.2MB)
테스트 4 〉	통과 (4.93ms, 10.2MB)
테스트 5 〉	통과 (33.14ms, 10.5MB)
테스트 6 〉	통과 (1.62ms, 10.2MB)
테스트 7 〉	통과 (8.38ms, 10.1MB)
테스트 8 〉	통과 (0.24ms, 10.2MB)
테스트 9 〉	통과 (2.00ms, 10.3MB)
테스트 10 〉	통과 (0.16ms, 10.2MB)
테스트 11 〉	통과 (0.65ms, 10.2MB)
테스트 12 〉	통과 (0.22ms, 10.4MB)
테스트 13 〉	통과 (2.18ms, 10.3MB)
테스트 14 〉	통과 (1.88ms, 10.2MB)
테스트 15 〉	통과 (0.64ms, 10.3MB)
테스트 16 〉	통과 (0.01ms, 10.3MB)
테스트 17 〉	통과 (0.01ms, 10.2MB)
테스트 18 〉	통과 (0.78ms, 10.3MB)
테스트 19 〉	통과 (0.12ms, 10.2MB)
테스트 20 〉	통과 (0.34ms, 10.3MB)
테스트 21 〉	통과 (0.12ms, 10.3MB)
테스트 22 〉	통과 (1.04ms, 10.5MB)
테스트 23 〉	통과 (0.58ms, 10.3MB)
테스트 24 〉	통과 (0.95ms, 10.2MB)
테스트 25 〉	통과 (0.50ms, 10.3MB)
테스트 26 〉	통과 (0.41ms, 10.1MB)
테스트 27 〉	통과 (0.77ms, 10.2MB)


h = 현재 문자열과 목표 문자열의 차이
테스트 1 〉	통과 (0.28ms, 10.3MB)
테스트 2 〉	통과 (1.09ms, 10.2MB)
테스트 3 〉	통과 (0.16ms, 10.2MB)
테스트 4 〉	통과 (2.82ms, 10.4MB)
테스트 5 〉	통과 (13.72ms, 10.3MB)
테스트 6 〉	통과 (1.12ms, 10.4MB)
테스트 7 〉	통과 (2.29ms, 10.3MB)
테스트 8 〉	통과 (0.16ms, 10.4MB)
테스트 9 〉	통과 (1.21ms, 10.3MB)
테스트 10 〉	통과 (0.24ms, 10.1MB)
테스트 11 〉	통과 (0.46ms, 10.3MB)
테스트 12 〉	통과 (0.24ms, 10.3MB)
테스트 13 〉	통과 (4.53ms, 10.3MB)
테스트 14 〉	통과 (3.01ms, 10.3MB)
테스트 15 〉	통과 (0.57ms, 10.3MB)
테스트 16 〉	통과 (0.01ms, 10.3MB)
테스트 17 〉	통과 (0.01ms, 10.4MB)
테스트 18 〉	통과 (1.09ms, 10.3MB)
테스트 19 〉	통과 (0.10ms, 10.2MB)
테스트 20 〉	통과 (0.30ms, 10.2MB)
테스트 21 〉	통과 (0.09ms, 10.3MB)
테스트 22 〉	통과 (2.92ms, 10.3MB)
테스트 23 〉	통과 (0.66ms, 10.4MB)
테스트 24 〉	통과 (1.17ms, 10.3MB)
테스트 25 〉	통과 (0.63ms, 10.2MB)
테스트 26 〉	통과 (0.38ms, 10.3MB)
테스트 27 〉	통과 (0.41ms, 10.4MB)