[BOJ 20914 // C++] QWERTY 자판

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 20914번 문제인 QWERTY 자판이다.
문제는 아래 링크를 확인하자.

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

 

주어진 그림의 자판을 각 키를 정점으로, 서로 인접한 관계에 있는 키의 쌍의 관계를 에지로 갖는 그래프로 모델링하면 어떤 키를 누른 뒤 다음 키를 누를 때까지 걸리는 이동시간을 이 그래프 위에서의 최단거리를 이용해 구할 수 있게 된다.

 

정점의 개수가 충분히 적으므로 글쓴이는 Floyd-Warshall 알고리즘을 이용해 각 키 사이의 이동거리를 전처리하려 문제를 해결하였다. 각 키를 시작점으로 하는 BFS 등을 이용해도 문제를 충분히 해결할 수 있을 것이다.

 

인접한 두 키 정보를 기록할 때 특히 신경써서 빠진 정보가 없게끔 유의하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

int dist[128][128];
int Q, N, ans;
string s;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	memset(dist, 0x3f, sizeof(dist));
	for (char i = 'A'; i <= 'Z'; i++) dist[i][i] = 0;
	dist['Q']['W'] = dist['W']['E'] = dist['E']['R'] = dist['R']['T'] = dist['T']['Y'] = dist['Y']['U'] = dist['U']['I'] = dist['I']['O'] = dist['O']['P'] = 1;
	dist['A']['S'] = dist['S']['D'] = dist['D']['F'] = dist['F']['G'] = dist['G']['H'] = dist['H']['J'] = dist['J']['K'] = dist['K']['L'] = 1;
	dist['Z']['X'] = dist['X']['C'] = dist['C']['V'] = dist['V']['B'] = dist['B']['N'] = dist['N']['M'] = 1;
	dist['Q']['A'] = dist['A']['Z'] = dist['W']['S'] = dist['S']['X'] = dist['E']['D'] = dist['D']['C'] = dist['R']['F'] = dist['F']['V'] = dist['T']['G'] = dist['G']['B'] = dist['Y']['H'] = dist['H']['N'] = dist['U']['J'] = dist['J']['M'] = dist['I']['K'] = dist['O']['L'] = 1;
	dist['W']['A'] = dist['E']['S'] = dist['S']['Z'] = dist['R']['D'] = dist['D']['X'] = dist['T']['F'] = dist['F']['C'] = dist['Y']['G'] = dist['G']['V'] = dist['U']['H'] = dist['H']['B'] = dist['I']['J'] = dist['J']['N'] = dist['O']['K'] = dist['K']['M'] = dist['P']['L'] = 1;

	for (char i = 'A'; i <= 'Z'; i++) {
		for (char j = 'A'; j <= 'Z'; j++) {
			if (dist[i][j] == 1) dist[j][i] = 1;
		}
	}

	for (char k = 'A'; k <= 'Z'; k++) {
		for (char i = 'A'; i <= 'Z'; i++) {
			for (char j = 'A'; j <= 'Z'; j++) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

	cin >> Q;
	while (Q--) {
		cin >> s; N = s.length(); ans = 0;
		for (int i = 0; i + 1 < N; i++) ans += dist[s[i]][s[i + 1]];
		cout << ans * 2 + N << '\n';
	}
}