백준 1240 c++ "노드사이의 거리" -PlusUltraCode-

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

 

[필자 사고]

그래프 문제이다.

단순히 특정 노드사이의 거리를 요구하는 문제이므로 너비우선 탐색인 BFS탐색으로 문제를 해결했다.

매번 방문배열을 체크해서 방문한 곳은 true를 처리하고 특정 지점에 도달할 경우 그동안의 weight을 반환한다.

BFS 너비우선탐색 기본 문제로 좋은거 같다.

[코드 해설]

1. 입력 처리 (Input 함수)

Input() 함수는 그래프 정보를 입력받아 인접 리스트 형태로 저장하는 역할을 합니다.

• 먼저, 노드 개수 N과 쿼리 개수 M을 입력받습니다.
• arr 벡터를 크기 N+1로 초기화하여 1번 노드부터 접근할 수 있도록 합니다.
• visited 벡터 역시 크기 N+1로 설정하여 방문 여부를 관리합니다.
• N-1개의 간선을 입력받아 무방향 그래프를 구성합니다.
  • 각 노드는 (연결된 노드, 가중치) 형태로 저장됩니다.
  • 양방향 그래프이므로 arr[start]와 arr[end]에 각각 값을 추가합니다.

---

2. BFS 탐색 (BFS 함수)

BFS() 함수는 **너비 우선 탐색(BFS)**을 활용하여 **시작점에서 목표점까지의 최단 거리(가중치 합)**를 계산하는 역할을 합니다.

1. 초기 설정
   • queue<Node> myQueue를 선언하여 BFS 탐색을 위한 큐를 생성합니다.
   • start 노드를 큐에 {start, 0} 형태로 넣고, visited[start] = true로 방문 표시합니다.
2. BFS 탐색 과정
   • 큐에서 현재 노드(nowStart)와 **누적 가중치(nowWeight)**를 꺼냅니다.
   • 만약 nowStart가 목표 노드 end라면, 최단 거리(가중치 합)를 출력하고 종료합니다.
   • 현재 노드에 연결된 모든 인접 노드를 확인합니다.
     • 만약 방문한 적 없는 노드라면, 현재까지의 거리 + 가중치를 누적하여 큐에 삽입합니다.
     • 삽입과 동시에 visited[nextIdx] = true로 설정하여 중복 방문을 방지합니다.

---

3. 게임 실행 (Game_Start 함수)

Game_Start() 함수는 M개의 거리 계산 쿼리를 처리하는 역할을 합니다.

1. M개의 쿼리를 반복 수행
   • visited 벡터를 clear()한 후 resize(N + 1)하여 매 쿼리마다 방문 기록을 초기화합니다.
   • start와 end 값을 입력받아 BFS(start, end)를 실행하여 **최단 거리(가중치 합)**를 출력합니다.

[소스 코드]

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

	using namespace std;
	typedef pair<int, int> Node;
	vector<vector<Node>> arr;
	vector<bool> visited;
	int N, M;

	void Input() {
		cin >> N >> M;
		arr.resize(N + 1);

		visited.resize(N + 1);

		for (int i = 0; i < N - 1; i++) {
			int start, end, weight;
			cin >> start >> end >> weight;
			arr[start].push_back({ end,weight });
			arr[end].push_back({ start,weight });
		}
	}

	void BFS(int start, int end) {
		queue<Node> myQueue;
		myQueue.push({start,0});
		visited[start] = true;
		while (!myQueue.empty()) {
			int nowStart = myQueue.front().first;
			int nowWeight = myQueue.front().second;
			myQueue.pop();
			if (nowStart == end) {
				cout << nowWeight << '\n';
				return;
			}
			for (Node nextNode : arr[nowStart]) {
				int nextIdx = nextNode.first;
				int Weight = nextNode.second;

				if (visited[nextIdx] == true)continue;
				myQueue.push({ nextIdx,nowWeight + Weight });
				visited[nextIdx] = true;
			}
		}
	}

	void Game_Start() {
		for (int i = 0; i < M; i++) {
			visited.clear();
			visited.resize(N + 1);
			int start, end;
			cin >> start >> end;
			BFS(start, end);

		}
	}

	int main(void) {
		Input();
		Game_Start();
	}