[C++]프로그래머스 숫자 변환하기(BFS)

코딩테스트 연습 - 숫자 변환하기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

참고 코드

[C++ 프로그래머스] 숫자 변환하기 (tistory.com)

[C++ 프로그래머스] 숫자 변환하기

 

 

#include <string>
#include <vector>
#include <queue>
#include <set>
using namespace std;

int solution(int x, int y, int n)
{
	int answer = 0;
	if (x == y)
		return 0;

	queue<pair<int,int>> queue; //queue를 만드는데 이는 int pair로 이루어져있음.(보통 bfs를 쓸때 많이 쓰는 형태)
	set<int> set;

	set.insert(x);//중복값 체크용
	queue.push({x,0});//queue의 맨 윗 줄은 count가 0이며, x라는 숫자를 가지고 있다.

	while (!queue.empty())//큐가 빌 때까지 진행함(보통은 이 전에 break문으로 끝날것.)
	{
		auto data = queue.front();//첫번째로 참조할 데이터는 현재 queue에서 가장 꼭대기에 위치한 값
		queue.pop();//꺼낸 뒤 pop으로 꺼내줘야 한다.(원래 BFS가 그러함)

		if (data.first == y)//조건에 맞을 때
		{
			answer = data.second;//answer은 현재 count가 되고, while문은 즉시 종료(bfs는 최소경로를 구할 때 그 깊이 자체가 답이 되므로 이것이 가능)
			break;
		}
		else if (data.first < y)//조건에 맞지 않을 때
		{
			int X2 = data.first * 2;
			if (set.insert(X2).second)//set으로 이미 탐색한 데이터인지 판단한다.
			{
				queue.push({ data.first * 2,data.second + 1 });//삽입 성공한 경우 겹치는 값이 아니므로 queue에 넣어주고 count도 증가시켜준다.
			}

			int X3 = data.first * 3;
			if(set.insert(X3).second)
				queue.push({ data.first * 3,data.second + 1 });
			
			int AddN = data.first + n;
			if(set.insert(AddN).second)
				queue.push({ data.first + n,data.second + 1 });
		}
	}

	if (answer == 0)
		return -1;

	return answer;
}

알고리즘 :: BFS 너비 우선 탐색 (C/C++ 구현), 탐색알고리즘 - IT에 취.하.개. (tistory.com)

알고리즘 :: BFS 너비 우선 탐색 (C/C++ 구현), 탐색알고리즘

bfs는 보통 위 사이트에 나와있는 것과 같이, queue를 삽입 삭제하면서 한 단계마다 진행되어야 한다.

[STL] Set 생성, 삽입, 삭제 등 사용법 (tistory.com)

[STL] Set 생성, 삽입, 삭제 등 사용법

또한, set은 기본 오름차순으로 정렬, 중복을 허용하지 않는 알고리즘이라 지금과 같은 경우에 쓰면 좋음.

C++ set 사용법과 설명... (tistory.com)

C++ set 사용법과 설명...

에서 나와있듯이, set의 first는 iterator의 값, second는 삽입 성공,삭제 여부를 나타내기 때문에 이를 if문의 조건으로 하면 삽입과 동시에 if문을 실행할 수 있따.

 

만일, set과 같은 방법으로 중복 여부를 따져주지 않는다면 시간초과가 발생한다.