BOJ 12906 : 새로운 하노이 탑

풀이

---

 

문제 풀어보기

 

BFS 유형 중에서 이런 STL 을 사용하는 경우가 별로 없어서 포스팅해봤습니다.

이 문제에선 Array, String, Map 함수들이 사용됩니다.

 

 

우선 map 을 보겠습니다.

map< key, value > '변수명'

의 방식으로 사용되며 조금 어려울 수도 있는 함수입니다.

 

 

보통 bfs 에서 check[][] 라는 배열을 통해서

방문했던 위치를 파악합니다.

하지만 그게 좌표처럼 간단한 값이 아닌 경우

지금처럼 'aabbc' 라는 문자를 탐색했었는지?? 를 파악해야 하는 경우

map 함수가 사용됩니다.

 

 

그리고 이 문제에서는 그러한 key 값으로 array<string, 3> 이라는 배열을 사용했네요.

굳이 array 를 사용한 이유는 자료형과 크기를 확정 지을 수 있기 때문입니다.

 

 

vector<string> 의 경우 배열의 크기가 자유로워서

key 값으로 쓰기에는 무리가 있어 보이네요.

 

 

마지막으로 string 입니다.

자주 사용했는데도 저는 자꾸 까먹네요.

string 에서도 push 와 pop 이 가능하고

맨 처음값(front) 와 맨 뒤에 값(back) 을 확인하는 게 가능하다는 것을.....

 

 

이 정도 개념과 bfs 개념만 있다면 주석을 보시면 파악이 되실 거라 생각합니다.

질문은 댓글에 ~

 

 

 

코드

---

#include <iostream>
#include <algorithm>
#include <queue>
#include <array>
#include <map>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int cnt[3];
	array <string, 3 > s;
	for (int i = 0; i < 3; i++) {
		cin >> cnt[i];
		// 0 일 경우 입력이 안들어오기 때문에
		// 직접 공백을 넣어준다.
		if (cnt[i] == 0) {
			s[i] = "";
		}
		// 이외에는 직접 입력
		else {
			cin >> s[i];
		}
	}

	int ans_count[3] = { 0, 0, 0 };
	// '++' 연산자 사용을 위해 '0' 초기화
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < cnt[i]; j++) {
			ans_count[s[i][j] - 'A']++;
			// 각 단어가 몇개인지 카운트
		}
	}
	
	// map< key, value >
	// array 자체를 key 로 사용하는 것이 포인트
	map< array<string, 3>, int > d;
	queue< array<string, 3> > q;
	q.push(s);
	d[s] = 0;

	while (!q.empty()) {
		auto now = q.front();
		q.pop();

		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (i == j) continue;
				if (now[i].length() == 0) continue;
				auto next = now;
				next[j].push_back(next[i].back());
				next[i].pop_back();
				if (d.count(next) == 0) {
					d[next] = d[now] + 1;
					q.push(next);

				}
			}
		}

	}

	array< string, 3> ans;
	// 정답이 들어있는 key 값을 구현
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < ans_count[i]; j++) {
			ans[i] += 'A' + i;
		}
	}
	// value 가 정답이 된다.
	cout << d[ans] << '\n';

	
	return 0;
}