백준1544 - 사이클 단어

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

1544번: 사이클 단어

방문처리 여부로 풀었다. 원소들이 같은 단어이면 true, 다른 단어이면 false로 방문 여부를 표시한 뒤 현재 원소가 과거에 같은 원소였었던 경우는 탐색을 하지 않고 과거에 같은 적이 없던 단어면 현재 위치에서 탐색하여 총 몇 종류의 단어가 존재하는지 센 문제다.

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

bool compare(string a, string b) {
	return a.size() > b.size();
}

int main() {
	int m;
	int cnt = 0;
	vector<string> v;
	vector<bool> visit;
	string s;

	//단어들을 세팅
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> s;
		v.push_back(s);
		visit.push_back(false);
	}

	//같은 단어가 있는지 검사
	for (int i = 0; i < v.size(); i++) {
		//과거에 같은적이 있었던 단어이면 무시
		if (visit[i]) { 
			continue;
		}
		string check = v[i]; //현재 단어를 미리 저장
		visit[i] = true; //현재 단어를 방문 처리

		//현재 찾을 단어를 시계 방향으로 회전
		for (int j = 0; j < check.size(); j++) {
			check = check + check[0]; //맨 앞을 뒤로 붙이고
			check.erase(0, 1); //맨 앞을 뽑는다.

			//현재 다음 원소부터 탐색
			for (int k = i + 1; k < v.size(); k++) {
				if (check == v[k]) { //같은 단어이면
					visit[k] = true; //방문 처리
				}
			}
		}

		cnt++; //단어의 갯수 증가
	}

	cout << cnt;
}