[백준] 1796 - 신기한 키보드 (G4)

https://www.acmicpc.net/problem/1796

1796번: 신기한 키보드

옛날에 봤을 땐 분명 골드5 문제였는데 어느샌가 골드4로 올라간 문제이다.
풀고나서 보니까 왜 누구는 골드5로, 누구는 실버1로 매겼는지 알 것 같았다.
문제 상황을 프로그래밍적으로? 정의하고 나면 되게 간단해지기 때문이다.
그런데 이 문제는 그 정의가 어려운 문제였다
그래서 나도 이 문제 난이도에 골드4를 줬다.

문제는 간단하다.
좌우버튼과 엔터 버튼만으로 구성된 키보드를 이용해
주어진 문자열을 알파벳 순서대로 최소한의 키 입력으로 출력하는 문제이다

문자열의 길이가 최대 50으로 작은 편이다.
나는 이 문제를 보고 그리디 종류의 발상 문제 정도로 보고 고민했는데
결국 답이 안나와서 알고리즘 분류를 보았다.

분류된 알고리즘은 DP였다.
이 문제를 어떻게 DP로 풀 수 있을지 고민한 결과는 다음과 같았다.

---

1. 같은 알파벳은 한 방향으로 이동하면서 출력해야 한다.

이 문제는 DP식을 세우기 전에 문제를 간단하게 바꿔줘야 했다.
이 문제에서 같은 알파벳을 출력할 땐 한 방향으로만 이동하면서 출력해야 한다.
즉 왼쪽 -> 오른쪽 으로 가든지 오른쪽 -> 왼쪽으로 가든지 하나를 정해야한다.

이 이유는 나름 간단한 방법으로 이해해보았다.
일단 aaaaa 라는 알파벳이 있다면 당연히 한쪽 방향으로 훑으면서 출력하는게 최소임이 당연하다.
문제는 이 같은 알파벳 사이에 다른 알파벳이 껴있을 때가 문제가 된다.

abaaa 와 같은 문자열이 있다고 해보자.
그러면 a를 어떤 순서대로 눌러야할까?
중간에 b를 누르기 위해 이동하는 횟수를 최소화하려면
b 양옆에 있는 a 중 하나를 마지막으로 누르는게 더 이득이지 않을까?
이런 고민을 하게 된다.

하지만 이 고민은 의미가 없다.
b를 향해 이동하는 과정은 어차피 어디에서 끝내더라도 해야하는 과정이다.
오히려 이 이동 횟수를 최소화하는 과정에서
현재 a를 다 누르는 데 필요한 키보드 입력 횟수가 불필요하게 증가할 수 있다.
수학적으로 증명하는게 제일 깔끔하겠지만 난 직관적으로 이렇게 이해했다.

문제 정의상 커서는 처음에 맨 왼쪽에 있으니 처음엔 그렇다고 치자.
그렇다면 a를 한 방향으로 다 눌렀는데 그 결과가 b의 중간지점이라면 그때는 어떻게 해야할까?
제일 가까운 b부터 눌러야할까?
아니면 b도 한 방향을 정해서 쭉 누르기 위해 양 끝점 중 하나로 이동해야할까?

답은 b의 양쪽 끝 중 한곳으로 이동해야한다.
제일 가까운 b를 누르더라도 어차피 지금 모든 b를 다 누르려면 양쪽 끝은 어차피 방문해야한다.
그렇다면 그냥 처음부터 한쪽을 골라서 방문하고 거기서부터 일직선으로 다 누르는게 낫다.

이렇게 문제를 축소하고나면 문제가 간단해진다.

알파벳 a를 출력할 때 좌/우 어떤 방향으로 이동하면서 출력할 것인가?
알파벳 b를 출력할 때 좌/우 어떤 방향으로 이동하면서 출력할 것인가?
..... 이하 반복 .....

최대 26개 선택지들의 조합의 결과 중 최소 입력횟수를 찾으면 된다.

---

2. 엔터는 사실 중요하지 않다.

이 문제에서 중요한 건 좌우 방향키의 최소 입력 횟수이다.
엔터는 어차피 한번씩 다 눌러야한다.
즉 엔터를 치는 횟수는 문제를 푸는 과정에서 고려할 필요가 없다.
마지막에 구한 횟수에서 문자열 길이만큼 횟수를 더해주면된다.

따라서 앞으로 구하는 DP값은 오직 이동 횟수만 고려한 값이다.

---

3. 축소된 문제를 풀기

이제 문제는 축소됐다.
각 알파벳을 출력할 때 어떤 방향으로 이동할 지 선택을 반복하면 된다.

알파벳 소문자가 26개이니 2^26 으로 경우의 수가 약 6천만이다.
제한 시간이 2초라서 26개의 순열을 만들어서 풀어도 되겠지만 나는 DP로 풀었다.
문제를 풀고나서 난이도를 매겨 보면 알겠지만 누군가는 이 문제를 브루트포스로 분류를 했는데,
그 이유가 아마 이것 때문인 것 같다.

그런데 이 문제의 의외의 어려운 점은 이걸 구현하는 데 있다.
저 6천만 경우의 수를 모두 탐색을 하기로 결정했다고 하더라도,
그 탐색하는 과정을 코드로 구현하는 난이도가 생각보다 간단하지 않다.
난 그게 이 문제의 난이도가 골드4까지 올라간 이유라고 생각한다.

이제부터 내가 구현한 과정을 설명해보고자 한다.

나는 DP테이블을 고민할 때
현재 눌러야 하는 알파벳을 다 출력했을 때 커서 위치가 왼쪽 끝인지 오른쪽 끝인지로 구분해서 생각했다.
그리고 DP테이블의 값은 당연히 키보드 입력 횟수이다.

DP[Now][Left] =
현재 눌러야하는 알파벳을 왼쪽 방향으로 출력했을 때 현재까지 누른 총 키보드 횟수

이렇게 정의를 하자.
실제로는 오른쪽 경우도 저장을 해야하는데, 원리는 왼쪽과 똑같으니 왼쪽만 생각을 해보자.
양쪽 방향을 다 저장하는 이유는 당장은 왼쪽방향으로 구한게 더 빠르더라도
그게 결과적으로는 최적해가 아닐 수 있기 때문이다.

구체적 예시를 들어 설명하기 위해
주어진 문자열에 알파벳 abcd가 종류별로 다 있는 상황에서
알파벳 b를 왼쪽으로 출력하는 경우의 수를 구한다고 생각해보자.

각 경우의 수를 구하기 위해, 키보드를 누르는 과정을 쪼개서 생각해보면
1) 현재 커서 위치를 현재 누를 알파벳의 양 끝 중 한 곳으로 이동시키고,
2) 그 끝에서부터 반대쪽 끝으로 이동시키면 된다

이 과정을 알파벳 b에 적용하면
알파벳 b를 왼쪽 방향으로 출력할 때까지 입력한 누적 키보드 입력 횟수는

(ㄱ) a를 출력하기 위해 커서를 이동했던 누적 횟수와
(ㄴ) 직전에 a를 다 출력한 뒤의 커서 위치에서 제일 오른쪽 b로 커서를 이동한 횟수와
(ㄷ) 제일 오른쪽 b부터 제일 왼쪽 b로 커서를 이동시킨 횟수의 합이다.

하지만 직전에 a를 출력할 때 왼쪽으로 이동하면서 했는지 오른쪽으로 이동하면서 했는지 모른다.
이 방향에 따라서 (ㄱ) 과 (ㄴ) 의 값이 달라지기 때문에
a의 이동 방향 별로 (ㄱ) 과 (ㄴ) 을 구하고, 이를 이용해 따로 결과 값을 계산하면 그 중 최솟값을 쓰면 된다.

이를 구하기 위해 필요한 정보는 4가지다.
a의 왼쪽 끝 위치 (a를 왼쪽 방향으로 이동시킨 경우 a의 최종 위치)
a의 오른쪽 끝 위치(a를 오른쪽 방향으로 이동시킨 경우 a의 최종 위치)
b의 왼쪽 끝 위치, b의 오른쪽 끝 위치 (ㄴ, ㄷ 을 구하기 위함)

이 정보를 모든 알파벳에 대해 일반화해보면
직전 알파벳의 왼쪽, 오른쪽 끝 위치
현재 알파벳의 왼쪽, 오른쪽 끝 위치를 이용해서
아까 정의한 DP를 이용해 아래와 같은 식으로 적을 수 있다.

DP[Now][Left] = min(
DP[Previous][Left] + distance[Previous_Left_Pos][Now_Right_Pos] + distance[Now_Right_Pos][Now_Left_Pos],
DP[Previous][Right] + distance[Previous_Right_Pos][Now_Right_Pos] + distance[Now_Right_Pos][Now_Left_Pos],
)

그런데 실제로 코딩할 때는 이 식도 복잡하다.
이 식을 더 간소화시켜보면 우리는 언제나 '직전의 값' 만 필요하다.
이를 이용하면 우리는 DP를 굳이 테이블이 아니라 왼쪽, 오른쪽 2개의 변수를 이용해서 구할 수 있다.

구현한 코드는 아래와 같다.

from collections import deque
UNSET = -1

s = input()
start = [UNSET for _ in range(26)]
end = [UNSET for _ in range(26)]

index = 0
for c in s:
  i = ord(c) - ord('a')
  if start[i] == UNSET:
    start[i] = index
    end[i] = index
  else:
    end[i] = index

  index += 1

index_list = [(0, 0)]
for i in range(len(start)):
  if start[i] != UNSET:
    index_list.append((start[i], end[i]))

LEFT = 0
RIGHT = 1
dp = [0, 0]
for i in range(1, len(index_list)):
  before_l = index_list[i-1][LEFT]
  before_r = index_list[i-1][RIGHT]
  now_l = index_list[i][LEFT]
  now_r = index_list[i][RIGHT]
  distance = abs(now_r - now_l)
  # 이번에 왼쪽에서 끝나려면
  # 직전왼쪽끝 -> 이번 오른쪽 -> 이번 왼쪽
  # 직전오른쪽 -> 이번 오른쪽 -> 이번 왼쪽
  after_l = min(dp[LEFT] + abs(now_r-before_l), dp[RIGHT] + abs(now_r-before_r)) + distance
  after_r = min(dp[LEFT] + abs(now_l-before_l), dp[RIGHT] + abs(now_l-before_r)) + distance
  
  dp[LEFT] = after_l
  dp[RIGHT] = after_r
  #print(dp)

print(min(dp)+len(s))

다시 봐도 이 문제는 구현이 참 어려운 것 같다.