[백준] QWERTY 자판 20914 python 풀이

핵심

• bfs 탐색시 자판의 행이 약간씩 비스듬히 있어서 살짝 햇갈리는 듯 보이지만
  그냥 직사각형으로 생각하고 한번 상하좌우 말고 어디또 갈수 있는지 보고 방향추가하면 어렵지않게 풀림
• 추가로 키보드 탐색범위가 넓지않아 시간초과도 고민하지 않아도 됨

"""
https://www.acmicpc.net/problem/20914
"""

import sys
from collections import deque
input = sys.stdin.readline

keyboards = [
    ['Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P'],
    ['A', 'S', 'D', 'F', 'G', 'H', 'J', 'K', 'L'],
    ['Z', 'X', 'C', 'V', 'B', 'N', 'M']
]

char_dict = dict() 
for y, r in enumerate(keyboards):
    for x, ch in enumerate(r):
        char_dict[ch] = (y, x)

dx = [0, 0, 1, -1, 1, -1]
dy = [1, -1, 0, 0, -1, 1]

def bfs(start, end):
    isVisited = [[False for _ in range(len(keyboards[0]))] for _ in range(3)]
    isVisited[1][-1] = True
    isVisited[2][-2] = isVisited[2][-3] = isVisited[2][-1] = True
    answer = 0

    cur_y, cur_x = char_dict[start][0], char_dict[start][1]
    q = deque()
    q.append([cur_y, cur_x, 0])
    while q:
        cur_y, cur_x, t = q.popleft()
        isVisited[cur_y][cur_x] = True
        if cur_y == char_dict[end][0] and cur_x == char_dict[end][1]:
            return t*2
        for i in range(6):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]
            if 0 <= next_x < 10 and 0 <= next_y < 3 and not isVisited[next_y][next_x]:
                q.append([next_y, next_x, t+1])
    return -1

def solve(w):
    answer = 1
    for i in range(1, len(word)):
        # move
        answer += bfs(w[i-1], w[i])
        # press
        answer += 1

    return answer

t = int(input())
for _ in range(t):
    word = input().strip()
    print(solve(word))