[BOJ][Python] 20914번 QWERTY 자판

1. 문제

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

20914번: QWERTY 자판

---

2. 문제 풀이 알고리즘

1) QWERTY 좌표 딕셔너리

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

 

QWERTY 키보드를 왼쪽으로 정렬하면 위의 표와 같이 되는데, 이 좌표를 그대로 qwerty 딕셔너리에 저장해준다.

qwerty = {"Q": [0, 0], "W": [0, 1], ... , "A": [1, 0], ... , "Z": [2, 0], ... , "M": [2, 6]}

qwerty = dict()
q_str = ["QWERTYUIOP", "ASDFGHJKL", "ZXCVBNM"]

for i in range(3):
    for j in range(len(q_str[i])):
        qwerty[q_str[i][j]] = [i, j]

 

2) 이동 시간 계산

현재 지점에서 다른 지점으로 이동할 때, 출발 지점으로부터 상하좌우, 대각선 관계에 있을 때 이동시간이 2초가 된다.

더 멀리 있는 지점으로 갈 때는 인접한 지점들로 2초씩 이동하며 출발지에서 도착지로 향하게 된다.

 

결국 출발지점 부터 도착지점까지 이동 시간은 (둘 사이의 위치 차이 X 2)초 라고 볼 수 있는데, 이 때 위치 차이는 이동할 때 대각선으로 이동이 가능하기 때문에 두 지점의 x, y 좌표 차이 중 더 큰 값이라고 볼 수 있다.

 

예를 하나 들어보면, "A" 에서 "R"로 이동한다고 하면 거쳐가야하는 최소 경로는 "A"-"S"-"D"-"R" 가 된다. A는 (1, 0), R은 (0, 3)인데 둘의 x 차이가 1, y차이가 3이기 때문에 위치 차이를 3이라고 볼 수 있다. 이는 최소 경로 개수 3개와 일치한다.

curr_time = max(abs(prev[0] - curr[0]), abs(prev[1] - curr[1]))

이 코드를 통해 해당 부분을 구현해 주었다.

 

하지만 오른쪽 아래 대각선 관계에 있는 지점간의 이동에서는 예외가 발생한다.

처음 딕셔너리를 만들 때 구상한 표로는 오른쪽 아래로 향하는 구조에서 대각선이기 때문에  거리가 1이 된다.

하지만 "Q" - "S"와 같이 오른쪽 대각선 아래에 있는 경우에는 서로 접하지 않기 때문에 거리는 1이 아닌 2가 되어야 한다. 그래서 이런 부분에 대해 예외 처리를 해주었다.

 

두 지점간에 바로 붙어 있는 것 뿐만아니라 오른쪽 아래로 이동하는 부분이 존재하는 모든 부분에 대하여 예외 처리를 해주어야 하는데, 이때 오른쪽 아래로 이동할 때는 두 지점 중 한 지점이 다른 지점보다 x, y 좌표 모두 크다는 특징이 있다. 

if (curr[0] - prev[0])*(curr[1] - prev[1]) > 0:
	curr_time += min(abs(prev[0] - curr[0]), abs(prev[1] - curr[1]))

위의 코드에서 이 부분을 구현해주었다. 오른쪽 아래로 갈 때마다 그 크기만큼 거리를 더해줄 수 있도록 하였다.

이렇게 거리를 구현하는 게 끝이 나면 아래 코드 처럼 한 칸 이동할 때 걸리는 시간이 2초이기 때문에 거리에 2를 곱해주고 머무르는 시간 1을 최종 시간에 누적하였다.

 

for _ in range(int(input().strip())):
    string = input().strip()
    prev = qwerty[string[0]]
    time = 1

    for c in string[1:]:
        curr = qwerty[c]
        curr_time = max(abs(prev[0] - curr[0]), abs(prev[1] - curr[1]))

        if (curr[0] - prev[0])*(curr[1] - prev[1]) > 0:
            curr_time += min(abs(prev[0] - curr[0]), abs(prev[1] - curr[1]))

        time += (2 * curr_time + 1)

        prev = curr
        
    print(time)

 

3) 전체 코드

import sys

input = sys.stdin.readline

qwerty = dict()
q_str = ["QWERTYUIOP", "ASDFGHJKL", "ZXCVBNM"]

for i in range(3):
    for j in range(len(q_str[i])):
        qwerty[q_str[i][j]] = [i, j]

for _ in range(int(input().strip())):
    string = input().strip()
    prev = qwerty[string[0]]
    time = 1

    for c in string[1:]:
        curr = qwerty[c]
        curr_time = max(abs(prev[0] - curr[0]), abs(prev[1] - curr[1]))

        if (curr[0] - prev[0])*(curr[1] - prev[1]) > 0:
            curr_time += min(abs(prev[0] - curr[0]), abs(prev[1] - curr[1]))

        time += (2 * curr_time + 1)

        prev = curr
        
    print(time)