급하게임개발

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

이 문제는 처음 보고 어떻게 풀어야지라는 생각이 너무들었다 골드 3부터는 여러알고리즘이 섞여 어떻게 딱풀어야지라고 생각이 안나는 거같다

이 문제는 일단 조합으로 우리는 2차원 배열에서 원소를 뽑아줄것이다 원소를 뽑을 때는 1차원 배열이라고 생각해서 뽑아야한다

즉 위표와 같이 0,0 은 0번 0,1은 1번 이라고 생각해야한다 이거를 구하는 방법은 다음과 같다
행/5 + 열%5 를 하면 몇번짼지 우리는 알수 있다 이를 바탕으로 우리는 일차원 배열에서 7개를 뽑은 후 해당 7개의 원소가 서로 이어져 있고 S의 갯수가 4보다 많은지만 검사하면 된다

검사는 우리가 조합으로 뽑은 7개의 원소를 bfs 로 검사한다 즉 bfs로 특정 방향들을 탐색 한다 만약 끊어져있는 부분이 생기면큐에 원소가 들어가지 않을 테니 연속되지 않음을 우리는 알수 있다 전체 코드는 아래와 같다

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

char grid[5][5];
int ans = 0;
bool isConnected(vector<int> selected) {
    int dx[4] = { -1,1,0,0 };
    int dy[4] = { 0,0,-1,1 };
    int cnt = 1;
    bool isVisited[25] = { false, };
    bool sel[25] = { false, };

    for (int i = 0; i < 7; i++) {
        sel[selected[i]] = true;
    }

    queue<int> bfsQ;
    bfsQ.push(selected[0]);
    isVisited[selected[0]] = true;

    while (!bfsQ.empty()) {
        int cur = bfsQ.front();

        int r = cur / 5;
        int c = cur % 5;

        bfsQ.pop();

        for (int i = 0; i < 4; i++) {
            int nr = r + dx[i];
            int nc = c + dy[i];
            if (nr < 0 || nr >= 5 || nc < 0 || nc >= 5)
                continue;
            int nxt = nr * 5 + nc;


            if (!isVisited[nxt] && sel[nxt]) {
                isVisited[nxt] = true;
                bfsQ.push(nxt);
                cnt++;
            }
        }
    }

    return cnt == 7;
}
void dfs(int start, int count, int sCount, vector<int> selected) {
    if (count == 7) {
        if (sCount >= 4 && isConnected(selected)) {
            ans += 1;
        }
        return;
    }
    if (sCount + (7 - count) < 4)
        return;

    for (int i = start; i < 25; i++) {
        int r = i / 5;
        int c = i % 5;

        selected.push_back(i);

        if (grid[r][c] == 'S') {
            dfs(i + 1, count + 1, sCount + 1, selected);
        }
        else {
            dfs(i + 1, count + 1, sCount , selected);
        }

        selected.pop_back();
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 5x5 격자 입력 받기
    for (int i = 0; i < 5; i++) {
        string line;
        cin >> line;
        for (int j = 0; j < 5; j++) {
            grid[i][j] = line[j];
        }
    }

    vector<int> selected;
    dfs(0, 0, 0, selected);
    cout << ans << "\n";

    return 0;
}

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

이 문제도 어느 게임회사 코테에 나왔던 문제였다 코테풀기전에 이문제를 풀었다면 좋았었을텐데 지금에서야 접했다

이문제는 사이클이 하나만 있다고 가정하고 그래프릍 탐색해서 순환 구조를 파악하는 문제이다 
첫 번째로 사이클을 탐색하는 규칙은 자신으로 왔을떄 자신의 이전 노드들을 저장하고 있는다 그리고 만약에 다음노드를 방문했을때 이노드가 방문되어있고 이노드에 저장되어있던 노드가 지금 노드와 다르다면 이노드는 순환구조를 만든 노드라고 파악한다

이에 대한 코드는 아래와 같다

void findCycle(int cur) {
	isVisited[cur] = true;
	for (int i = 0; i < vertex[cur].size(); i++) {
		if (hasCycle)
			return;
		int next = vertex[cur][i];
		if (isVisited[next]) {
			if (next != pre[cur]) {
				cycle[cur] = true;
				hasCycle = true;
				while (cur != next) {
					cycle[pre[cur]] = true;
					cur = pre[cur];
				}
				return;
			}
	
		}
		else {
			pre[next] = cur;
			findCycle(next);
		}
	}
}

이렇게 dfs를 통해 방문 한 노드에 대해서 이전노드들을 검사해준다 그후 순환 노드가 파악이되었으면 pre 배열을 통해 이전 노드들을 파악해서 cycle로 체크를 해준다


이제 cycle로부터 각 노드들이 얼만큼 떨어져 있는 지 계산한다

void bfs() {
	queue<pair<int, int>> q;

	for (int i = 1; i <= n; i++) {
		if (cycle[i]) {
			isVisited[i] = true;
			q.push({ i,0 });
		}
	}

	while (!q.empty()) {
		int cur = q.front().first;
		int dis = q.front().second;
		q.pop();

		isVisited[cur] = true;

		for (int i = 0; i < vertex[cur].size(); i++) {
			int next = vertex[cur][i];
			if (isVisited[next])
				continue;
			dist[next] = dis + 1;
			q.push({ next, dis + 1 });
		}
	}
}

bfs를 통해 판별한다

전체 코드는 아래와같다

#include <iostream>
#include <vector>
#include <queue>
#include<cstring>
using namespace std;
bool isVisited[3001];
int pre[3001];
bool cycle[3001];
int dist[3001];
vector<int> vertex[3001];
int n;
bool hasCycle;

void bfs() {
	queue<pair<int, int>> q;

	for (int i = 1; i <= n; i++) {
		if (cycle[i]) {
			isVisited[i] = true;
			q.push({ i,0 });
		}
	}

	while (!q.empty()) {
		int cur = q.front().first;
		int dis = q.front().second;
		q.pop();

		isVisited[cur] = true;

		for (int i = 0; i < vertex[cur].size(); i++) {
			int next = vertex[cur][i];
			if (isVisited[next])
				continue;
			dist[next] = dis + 1;
			q.push({ next, dis + 1 });
		}
	}
}
void findCycle(int cur) {
	isVisited[cur] = true;
	for (int i = 0; i < vertex[cur].size(); i++) {
		if (hasCycle)
			return;
		int next = vertex[cur][i];
		if (isVisited[next]) {
			if (next != pre[cur]) {
				cycle[cur] = true;
				hasCycle = true;
				while (cur != next) {
					cycle[pre[cur]] = true;
					cur = pre[cur];
				}
				return;
			}
	
		}
		else {
			pre[next] = cur;
			findCycle(next);
		}
	}
}
int main() {
	cin >> n;
	int tmp1, tmp2;
	for (int i = 0; i < n; i++) {
		cin >> tmp1 >> tmp2;
		vertex[tmp1].push_back(tmp2);
		vertex[tmp2].push_back(tmp1);
	}
	findCycle(1);
	memset(isVisited, false, 3001);
	bfs();
	for (int i = 1; i <= n; i++) {
		cout << dist[i] << ' ';
	}
}

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

이 문제는 겁나 복잡해보였지만 막상 풀고나니 이해하기 쉬웠다

그냥 두가지 케이스 빨간공 파란공 각각 움직인다음 겹칠때 혹은 구멍에 들어갈때의 조건식만 추가해주면 되었다

#include<iostream>
#include<string>
#include<queue>
using namespace std;
int arr[10][10];
struct INFO {
	int Rx, Ry, Bx, By, count;
};
int n, m;
INFO start;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
int visited[11][11][11][11] = { 0, };
int bfs() {
	queue<INFO> bfsQ;
	bfsQ.push(start);

	int ans = -1;
	visited[start.Rx][start.Ry][start.Bx][start.By] = 1;
	while (!bfsQ.empty()) {
		INFO cur = bfsQ.front();
		bfsQ.pop();
		if (cur.count > 10)break;

		if (arr[cur.Rx][cur.Ry] == 4 && arr[cur.Bx][cur.By] != 4) {
			ans = cur.count;
			break;
		}

		for(int i=0; i<4; i++){
			int nextRy = cur.Ry;
			int nextRx = cur.Rx;
			int nextBy = cur.By;
			int nextBx = cur.Bx;
			while (1) {
				if (arr[nextRx][nextRy] != 1 and arr[nextRx][nextRy] != 4) {
					nextRx += dx[i];
					nextRy += dy[i];
				}
				else {
					if (arr[nextRx][nextRy] == 1) {
						nextRx -= dx[i]; 
						nextRy -= dy[i]; //벽일 경우 이전위치로
					}
					break;
				}
			}

			//blue 구슬 벽이나 구멍일때까지 한 방향으로 이동함
			while (1) {
				if (arr[nextBx][nextBy] != 1 and arr[nextBx][nextBy] != 4) {
					nextBx += dx[i];
					nextBy += dy[i];
				}
				else {
					if (arr[nextBx][nextBy] == 1) {
						nextBx -= dx[i]; 
						nextBy -= dy[i]; //벽일 경우 이전위치로
					}
					break;
				}
			}

			//red와 blue가 겹칠 경우
			if (nextRx == nextBx and nextRy == nextBy) {
				if (arr[nextRx][nextRy] != 4) {
					int red_dist = abs(nextRx - cur.Rx) + abs(nextRy - cur.Ry);
					int blue_dist = abs(nextBx - cur.Bx) + abs(nextBy - cur.By);

					if (blue_dist > red_dist) {
						nextBx -= dx[i];
						nextBy -= dy[i];
					}
					else {
						nextRx -= dx[i];
						nextRy -= dy[i];
					}
				}
			}

			//방문여부 확인
			if (visited[nextRx][nextRy][nextBx][nextBy] == 0) {
				visited[nextRx][nextRy][nextBx][nextBy] = 1;
				INFO next;
				next.Rx = nextRx;
				next.Ry = nextRy;
				next.Bx = nextBx;
				next.By = nextBy;
				next.count = cur.count + 1;

				bfsQ.push(next);

			}
		}

	}
	return ans;
}

int main() {
	cin >> n >> m;
	string input;

	for (int i = 0; i < n; i++) {
		cin >> input;
		for (int j = 0; j < m; j++) {
			if (input[j] == '#') {
				arr[i][j] = 1;
			}
			else if (input[j] == 'R') {
				arr[i][j] = 2;
				start.Rx = i;
				start.Ry = j;
			}
			else if (input[j] == 'B') {
				arr[i][j] = 3;
				start.Bx = i;
				start.By = j;
			}
			else if (input[j] == 'O') {
				arr[i][j] = 4;
			}
		}
	}
	start.count = 0;
	cout << bfs();
}

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

이 문제의 경우 dfs로 풀이를 진행했다  이 문제를 풀 때 한가지 잘못 생각한점으 치즈 안의 공간은 실내온도에 접촉 한것이아니라는 것이었다.  문제에서 테두리에는 치즈가 없다고 명시해주었으므로 dfs혹은 bfs로 0,0 위치 와 연결된 공간들을 모두 -1  로 체크 해주었다 그후 dfs를 한번더 진행하여 치즈들중 외부공기 2층이랑 이어진 공간들에 대해서 다른 배열에 넣어서 계산해주고 다시 0,0부터 dfs를 돌려 외부공기를 체크해 주었다.

#include <iostream>
using namespace std;
int N, M;
int arr[100][100];
int willMelt[100][100];
int xIdx[4] = { 1,0,-1,0 };
int yIdx[4] = { 0,1,0,-1 };
bool isVisited[100][100] = { 0, };
bool canGo(int x, int y) {
	if (x < N && y < M && x >= 0 && y >= 0) {
		if (!isVisited[x][y] && (arr[x][y] == 1))
			return true;
		else
			return false;
	}
	else
		return false;
}
void copyArr(int arr[100][100], int arr2[100][100]) {
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++) {
			arr[i][j] = arr2[i][j];
		}
}
void dfs(int x, int y) {
	int zeroCount = 0;
	for (int i = 0; i < 4; i++) {
		if (arr[x + xIdx[i]][y + yIdx[i]] == -1) {
			zeroCount += 1;
		}
		if (canGo(x + xIdx[i], y + yIdx[i])) {
			isVisited[x + xIdx[i]][y + yIdx[i]] = true;
			dfs(x + xIdx[i], y + yIdx[i]);
		}
	}
	if (zeroCount >= 2) {
		willMelt[x][y] = 0;
	}

}
void airDfs(int x, int y) {
	arr[x][y] = -1;
	for (int i = 0; i < 4; i++) {
		if (x + xIdx[i] < N && y + yIdx[i] < M && x + xIdx[i] >= 0 && y + yIdx[i] >= 0 && !isVisited[x + xIdx[i]][y + yIdx[i]]&& (arr[x + xIdx[i]][y + yIdx[i]] == 0|| arr[x + xIdx[i]][y + yIdx[i]] == -1)) {
			isVisited[x + xIdx[i]][y + yIdx[i]] = true;
			arr[x + xIdx[i]][y + yIdx[i]] = -1;
			airDfs(x + xIdx[i], y + yIdx[i]);
		}
	}


}
void meltCheese() {
	copyArr(willMelt, arr);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (!canGo(i, j))
				continue;
			isVisited[i][j] = true;
			dfs(i, j);
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			isVisited[i][j] = false;
		}
	}
	copyArr(arr, willMelt);
}
bool isMelted() {
	int sum = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (arr[i][j] != -1)
				sum += 1;
		}
	}
	if (sum == 0)
		return true;
	else
		return false;
}
void process() {
	int year = 0;
	airDfs(0, 0);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			isVisited[i][j] = false;
		}
	}
	while (!isMelted()) {
		meltCheese();
		airDfs(0, 0);
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				isVisited[i][j] = false;
			}
		}
		year += 1;
	}
	cout << year;
}
int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> arr[i][j];
		}
	}
	process();
}

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

이 문제의 경우 bfs 문제이다 dfs로 풀어도 무방하다
나의 경우 이문제를 풀 때 &&의 순서를 잘못 써서 문제를 제출했을 때 틀렸었다

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
int arr[50][50];
bool isVisited[50][50];
queue<pair<int, int>> bfsq;
queue<pair<int, int>> visitedq;
int n, l, r;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
bool canGo(int x, int y, int nx, int ny) {
	if (nx >= 0 && nx < n && ny>=0 && ny < n && !isVisited[nx][ny]) {
		if (abs(arr[nx][ny] - arr[x][y])>=l && abs(arr[nx][ny] - arr[x][y])<=r) {
			return true;
		}
		return false;
	}
	else {
		return false;
	}
}
bool bfs(int sX, int sY) {
	bfsq.push({ sX,sY });
	visitedq.push({ sX,sY });
	isVisited[sX][sY] = true;

	int cx, cy , nx, ny ,population, nationCount;
	int avrPop=0;
	population = arr[sX][sY];
	nationCount = 1;
	while (!bfsq.empty()) {
		cx = bfsq.front().first;
		cy = bfsq.front().second;
		bfsq.pop();
		for (int i = 0; i < 4; i++) {
			nx = cx + dx[i];
			ny = cy + dy[i];
			if (canGo(cx, cy, nx,ny)) {
				bfsq.push({ nx, ny });
				visitedq.push({ nx, ny });
				isVisited[nx][ny] = true;
				population += arr[nx][ny];
				nationCount += 1;
			}
		}
	}
	avrPop = population / nationCount;

	while (!visitedq.empty()) {
		arr[visitedq.front().first][visitedq.front().second] = avrPop;
		visitedq.pop();
	}

	if (nationCount > 1)
		return false;
	else {
		isVisited[sX][sY] = false;
		return true;
	}
}
int main() {
	cin >> n >> l >> r;
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}

	while (true) {
		bool canBreak = true;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if(!isVisited[i][j])
					canBreak=bfs(i, j)&&canBreak;
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				isVisited[i][j] = false;
			}
		}
		if (canBreak)
			break;
		cnt += 1;
	}
	cout << cnt;

}

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

이 문제는 처음에 dfs로 만 풀었으나 시간초과 가 났다 이에 dp와 섞어서 풀어야 한다는 힌트를 보게 되었다

			dp[x][y] = dp[x][y] + dfs(x + xidx[i],y + yidx[i]);

dp의 점화식은 이와 같은데 그이유는 나는 내가 다음에 갈수 있는 경로들이 갈수 있는 경로들의 합으로 표현할수 있기 때문이다

나는 dp배열을 -1로초기화를 해주었는데 그이유는 방문하지 않았다는 표시를 -1로 하게되었습니다 0은 방문은 했으나 해당 영역을 통해서 경로를 찾을 수 없는 것이라고 결정 하였습니다. 경로를 탐색하러 들어갔을 때 이미 해당 노드를 방문 한적이 있으면 해당 노드를 통해서 방문했던 길의 갯수가 해당 노드의 저장이 되어있기에 해당 노드의 값을 그대로 반환해주었습니다.

#include <iostream>
#include <set>
using namespace std;
int arr[500][500];
int dp[500][500];
int m, n;
int cnt;
int xidx[4] = { 1,0,-1,0 };
int yidx[4] = { 0,1,0,-1 };
bool canGo(int x, int y, int height) {
	if (x >= 0 && x < m && y>=0 && y < n && height > arr[x][y])
		return true;
	else
		return false;
}

int dfs(int x,int y) {
	if (x == m - 1 && y == n - 1) {
		return 1;
	}
	if (dp[x][y] != -1)
	{
		return dp[x][y];
	}

	dp[x][y] = 0;
	for (int i = 0; i < 4; i++) {
		if (canGo(x + xidx[i], y + yidx[i], arr[x][y])) {
			dp[x][y] = dp[x][y] + dfs(x + xidx[i],y + yidx[i]);
		}
	}
	return dp[x][y];
}
int main() {
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			dp[i][j] = -1;
		}
	}
	cout << dfs(0, 0);
}

전체 로직은 위와 같다

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

이 문제는 솔직히 설명이 겁나 불친절하다 

정확히 이문제는 핵심이 나를 기준으로 나보다 크기가 작고 같은 거리에 있는 물고기 들은 위에에서 왼쪽부터 오른쪽 까지 검사하고 내려와서 왼쪽부터 오른쪽 까지 검사하면서 이 순으로 탐색을 하는 거였다.
단 위에를 듣고 BFS  이동방향을 1,0 ->0,-1 ->0,1 ->-1,0 이렇게 만 하면 안풀린다

while (!bfsQ.empty()) {
		
				otherX = bfsQ.front().second.first;
				otherY = bfsQ.front().second.second;
				otherCost = bfsQ.front().first;
				if (CanEat(otherX, otherY) && otherCost<=cost) {
					if (otherX < startX) {
						startX = otherX;
						startY = otherY;
						otherCost = cost;
					}
					else if (otherX == startX && startY>otherY ) {
						startX = otherX;
						startY = otherY;
						otherCost = cost;
					}
				}

핵심은 이부분이다 내가 물고기를 먹을 수있는 지역으로 갔을 때 현재 큐에  들어와 있는 것중 나보다 거리가 작거나 같고 행의 값이  위에 있거나 혹은 행이 같다면 열값이 더 먼저인 애를 찾아서 거기를 가야한다 이에 의해 필자는 행을 검사에서 위에있으면 해당 행으로 탐색지점을 바꿔줬고 같다면 열값이 더 작은 쪽으로 옮겨줬다

#include <iostream>
#include <queue>
using namespace std;
int n;
int arr[20][20] = { 0, };
bool isVisited[20][20];
int fishSize = 2;
int eatFish = 0;
int cnt = 0;
queue<pair<int,pair<int, int>>>  bfsQ;

bool CanEat(int x, int y) {
	if (arr[x][y]>0&&arr[x][y] < fishSize) {
		return true;
	}
	return false;
}
bool canGo(int x, int y) {
	if (x >= 0 && x < n && y >= 0 && y < n && !isVisited[x][y] && (CanEat(x, y) || arr[x][y] == 0 || arr[x][y]==fishSize))
		return true;
	else
		return false;
}

void Bfs(int x, int y) {
	bfsQ.push({ cnt,{x,y} });
	arr[x][y] = 0;
	int startX, startY, cost;
	int otherX, otherY, otherCost;
	while (!bfsQ.empty()) {
		startX = bfsQ.front().second.first;
		startY = bfsQ.front().second.second;
		cost = bfsQ.front().first;
		bfsQ.pop();
		if (CanEat(startX, startY)) {
			cnt += cost;
			while (!bfsQ.empty()) {
		
				otherX = bfsQ.front().second.first;
				otherY = bfsQ.front().second.second;
				otherCost = bfsQ.front().first;
				if (CanEat(otherX, otherY) && otherCost<=cost) {
					if (otherX < startX) {
						startX = otherX;
						startY = otherY;
						otherCost = cost;
					}
					else if (otherX == startX && startY>otherY ) {
						startX = otherX;
						startY = otherY;
						otherCost = cost;
					}
				}

				bfsQ.pop();
				
			}
			bfsQ.push({ 0, {startX, startY}});
			eatFish += 1;
			if (eatFish == fishSize) {
				fishSize += 1;
				eatFish = 0;
			}
			arr[startX][startY] = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					isVisited[i][j] = false;
				}
			}
			isVisited[startX][startY] = true;
			cost = 0;
		}

		if (canGo(startX-1,startY)) {
			bfsQ.push({ cost + 1,{startX -1,startY}});
			isVisited[startX - 1][startY] = 1;
		}
		if (canGo(startX, startY-1)) {
			bfsQ.push({ cost + 1,{startX ,startY - 1} });
			isVisited[startX][startY-1] = 1;
		}
		if (canGo(startX , startY+1)) {
			bfsQ.push({ cost + 1,{startX ,startY + 1} });
			isVisited[startX][startY + 1] = 1;
		}
		if (canGo(startX+1 , startY)) {
			bfsQ.push({ cost + 1,{startX + 1,startY} });
			isVisited[startX + 1][startY] = 1;
		}
	}

}
int main() {
	cin >> n;
	int startIdxCol, startIdxRow;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 9) {
				startIdxCol = i;
				startIdxRow = j;
			}
		}
	}

	Bfs(startIdxCol, startIdxRow);
	cout << cnt;
}

#include <queue>
#include <iostream>
#include <string>
#include <cstring>

using namespace std;

int a, b;
bool visited[10000];
int logicD(int num) {
    return (num * 2) % 10000;
}

int logicS(int num) {
    return num - 1 < 0 ? 9999 : num - 1;
}

int logicL(int num) {
    return (num % 1000) * 10 + (num / 1000);
}

int logicR(int num) {
    return num / 10 + (num % 10) * 1000;
}
void bfs()
{
    queue<pair<int, string>> q;
    q.push(make_pair(a, ""));
    visited[a] = true;

    while (!q.empty())
    {
        int cur_num = q.front().first;
        string cur_op = q.front().second;
        q.pop();

        if (cur_num == b)
        {
            cout << cur_op << '\n';
            return;
        }

        int D, S, L, R;
        D = logicD(cur_num);
        if (!visited[D])
        {
            visited[D] = true;
            q.push(make_pair(D, cur_op + "D"));
        }
        S = logicS(cur_num);
        if (!visited[S])
        {
            visited[S] = true;
            q.push(make_pair(S, cur_op + "S"));
        }
        L = logicL(cur_num);
        if (!visited[L])
        {
            visited[L] = true;
            q.push(make_pair(L, cur_op + "L"));
        }
        R = logicR(cur_num);
        if (!visited[R])
        {
            visited[R] = true;
            q.push(make_pair(R, cur_op + "R"));
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int T;
    cin >> T;

    while (T--)
    {
        cin >> a >> b;
        memset(visited, false, sizeof(visited)); // 초기화
        bfs();
    }

    return 0;
}

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

이 문제는 최소시간을 구하는 것이기에 BFS로 조건을 만족시켰을 경우 바로 출력할 수있도록 코드를 작성하여야 합니다