백준 14226 c++ "이모티콘" -PlusUltraCode-

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

[필자 사고]

BFS탐색 문제입니다.

특히 너비우선 탐색이라 최소값을 찾는 대표적인 문제라고 생각이 드네요

이 문제에서 느낀 매력적이 포인트는 moniter 와 copyBoard를 이용하여 visted를 관리하는 방식이였습니다

언뜻보면 visited를 1차원으로 해결할 거라 생각하지만 실제로 2차원배열을 설정하여 2가지 값에 해당하게 방문 배열을 설정해야 문제를 해결할 수 있습니다.

 

또한 범위 관련해서 주의를 해야 되는데 2000을 마지노선으로 정한 이유는 해당 S값이 1000으로 되어있어 1000의 2배는 2천이라 해당 숫자로 범위를 정했습니다.

 

아래는 자세한 소스코드 해설입니다.

[코드 해설]

 

• 구조체 정의 및 변수 선언
  • struct img는 현재 모니터에 표시된 숫자(moniter), 클립보드에 복사된 숫자(copyBoard), 그리고 실행된 연산 횟수(count)를 저장하는 구조체이다.
  • S는 목표 숫자를 저장하는 변수이며, visited는 방문 여부를 확인하는 2차원 벡터이다.
• 입력 처리 및 초기화 (Game_Start 함수)
  • cin >> S;를 통해 목표 숫자를 입력받는다.
  • visited 벡터를 크기 2000×2000으로 초기화하여, 모든 상태를 방문하지 않은 것으로 설정한다.
  • BFS(1);을 호출하여 BFS 탐색을 시작한다.
• BFS 탐색 (BFS 함수)
  • queue<img>를 사용하여 BFS를 수행한다.
  • 초기 상태(모니터에 1이 표시되고 클립보드가 비어있는 상태)를 큐에 넣고 방문 처리한다.
  • 큐에서 상태를 꺼내 현재 moniter 값이 목표 S와 같으면 연산 횟수를 출력하고 종료한다.
  • 세 가지 연산을 수행하여 새로운 상태를 큐에 추가한다:
    1. 모니터 내용을 클립보드에 복사 (moniterCopyToBoard 함수)
       • 모니터 값을 클립보드에 복사한다.
       • 복사 후 클립보드 값이 1000을 초과하면 무시한다.
       • 방문하지 않은 상태라면 큐에 추가하고 방문 처리한다.
    2. 클립보드 내용을 모니터에 추가 (boardToMoniter 함수)
       • 현재 클립보드 값을 모니터에 추가한다.
       • 추가 후 모니터 값이 1999를 초과하면 무시한다.
       • 방문하지 않은 상태라면 큐에 추가하고 방문 처리한다.
    3. 모니터에서 1을 삭제 (deleteFromMoniter 함수)
       • 모니터 값에서 1을 감소시킨다.
       • 모니터 값이 0 미만이면 무시한다.
       • 방문하지 않은 상태라면 큐에 추가하고 방문 처리한다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
typedef pair<int, int> Node;
typedef struct img {
	int moniter;
	int copyBoard;
	int count;
};
int S;
vector<vector<bool>> visited;

void moniterCopyToBoard(int moniter,int board,int count, queue<img>& myQueue) {
	 board = moniter;
	 if (board > 1000)return;
	if (visited[moniter][board] == true)return;

	myQueue.push({ moniter,board, count+1 });
	visited[moniter][board] = true;
}
void boardToMoniter(int moniter, int board, int count, queue<img>& myQueue) {
	moniter += board;
	if (moniter > 1999)return;
	if (visited[moniter][board] == true) return;
	myQueue.push({ moniter,board ,count+1});
	visited[moniter][board] = true;
}
void deleteFromMoniter(int moniter, int board, int count, queue<img>& myQueue) {
	moniter--;
	if (moniter < 0)return;
	if (visited[moniter][board] == true) return;
	myQueue.push({ moniter,board,count+1 });
	visited[moniter][board] = true;
}

void BFS(int start) {
	queue<img> myQueue;
	myQueue.push({ start,0,0 });
	visited[start][0] = true;

	while (!myQueue.empty()) {
		int nowMoninter = myQueue.front().moniter;
		int nowCopyBoard = myQueue.front().copyBoard;
		int nowCount = myQueue.front().count;
		myQueue.pop();

		if (nowMoninter == S) {
			cout << nowCount << '\n';
			return;
		}
		
		moniterCopyToBoard(nowMoninter, nowCopyBoard, nowCount, myQueue);
		boardToMoniter(nowMoninter, nowCopyBoard, nowCount, myQueue);
		deleteFromMoniter(nowMoninter, nowCopyBoard, nowCount, myQueue);
	}
}

void Game_Start() {
	cin >> S;
	visited.assign(2000, vector<bool>(2000, false));
	BFS(1);
}

int main(void) {
	Game_Start();
}