백준 9019 C++ bfs

9019번: DSLR

 

문제 코드만 궁굼하시면 아래로 스크롤 해주세요~!

이 문제는 처음보는 문제 유형이였습니다.

왜냐하면 대부분의 그래프 문제는 vertex, edge의 개수가 정확히 주어지는 문제였는데

이번에는 implicit graph로 무한그래프? 끝을 알 수 없는 그래프 문제입니다.

 

저는 그래프 문제를 풀 때 기본적인 것으로 돌아가는게 중요하다 생각합니다.

그러므로 bfs에 대한 기본적인 코드를 머리에 넣고 갑시다. 

기본적으로 큐로 도착하고 가까운 노드를 먼저 탐색을 하니 아래와 같은 코드가 나옵니다....

// 그래프를 인접 리스트로 표현
vector<vector<int>> graph;
vector<bool> visited;

void bfs(int start) {
    queue<int> q;         // 탐색을 위한 큐
    q.push(start);        // 시작 노드를 큐에 넣음
    visited[start] = true; // 시작 노드를 방문 처리

    while (!q.empty()) {
        int current = q.front();  // 현재 노드
        q.pop();
        cout << current << " ";   // 현재 노드 방문 시 처리 (출력)

        // 현재 노드와 연결된 모든 이웃 노드를 탐색
        for (int neighbor : graph[current]) {
            if (!visited[neighbor]) {      // 방문하지 않은 이웃 노드일 경우
                q.push(neighbor);          // 큐에 추가
                visited[neighbor] = true;  // 방문 처리
            }
        }
    }
}

 

그럼 bfs의 인사이트를 통해서 위 문제에 접근해봅시다.

네가지 DSLR을 통해서

D -> DSLR

S  -> DSLR

L  -> DSLR

R  -> DSLR

이렇게 계속해서 DSLR마다 각각의 경우의 수를 찾아야합니다..

끝이 어딘지 모르고 계속해서 많은 경우가 나옵니다. 아.. 살짝 영감이 떠오르네요....

왠지 트리구조와 비슷할 것 같지 않나요?

 

만약 dsf를 통해서 접근하면 처음에 길을 잘 못 들으면 망하겠죠?

그래서 bsf를 통해서 다양한 루트를 찾는겁니다.

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

using namespace std;

string bfs(int start, int end){

	vector<bool> visited(10000, false);
	queue<pair<int, string>> q;


	q.push({ start, "" });
	visited[start] = true;


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

		if (current == end)
			return command;

		int D = (current * 2) % 10000;
		if (!visited[D]) {
			visited[D] = true;
			q.push({ D,command + 'D'});
		}

		int S = current == 0 ? 9999 : current - 1;
		if (!visited[S]) {
			visited[S] = true;
			q.push({ S,command + 'S' });
		}

		int L = (current % 1000) * 10 + current / 1000;
		if (!visited[L]) {
			visited[L] = true;
			q.push({ L,command + 'L' });
		}

		int R = current / 10 + (current % 10) * 1000;
		if (!visited[R]) {
			visited[R] = true;
			q.push({R,command + 'R' });
		}

	}

	return "";

}

int main() {

	int c;
	cin >> c;
	for (int i = 0; i < c; i++) {
		int st, end;
		cin >> st >> end;
		cout << bfs(st, end) << endl;

	}

	return 0;
}

 

 

저는 솔직히 제가 똑똑하다는 생각을 하지 않습니다. 그냥 일반적인 사고력을 가지고 있다고 생각합니다. 처음에는 브론즈 문제도 잘 못 풀었지만 step by step으로 접근하다 보니 조금씩 보이는 것 같습니다. 아직 골드문제는 제대로 풀지 못하지만 이짓을 졸업전까지 계속하다 보면 익숙해지겠죠? 새로운 놈이랑 싸워서 이길 자신이 없다면 비슷하지만, 조금이나마 익숙한 놈이랑 싸우며 트레이닝을 해봅시다. 뭐 인생은 마라톤이니까.

너무 성급해하지 말고 인생을 즐기면서 Better than yester day~~