[CPP] 백준 11403

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

11403번: 경로 찾기

이 문제의 경우 전형적인 BFS 문제이다

자기와 연결되어 있는 루트를 BFS로 계속 따라가며 이어져있는 모든 점에 대해 표시만 해주면 되는 쉬운 문제다

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

using namespace std;
int N;
int arr[100][100];
int ans[100][100];
void solution(int vertex) {
	queue<pair<int, int>> bfsq;
	for (int i = 0; i < N; i++) {
		if (arr[vertex][i] == 1) {
			bfsq.push({ vertex, i });
			ans[vertex][i] = 1;
			while (!bfsq.empty()) {
				int start = bfsq.front().first;
				int end = bfsq.front().second;
				bfsq.pop();
				for (int j = 0; j < N; j++) {
					if (arr[end][j] == 1 &&ans[vertex][j]==0) {
						bfsq.push({ end,j });
						ans[vertex][j] = 1;
					}
				}
				
			}
		}
		
	}

}
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j];
		}
	}

	for (int i = 0; i < N; i++) {
		solution(i);
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << ans[i][j]<<" ";
		}
		cout << endl;
	}
}

solution 함수를 설명을 하자면 solution  함수를 실행하면 매게변수로 vertex 즉 시작점이 넘어간다

그 후 arr를 참고하여 나와 연결되어있는 애들을 차례로 큐에 넣어준 후 차례로 pop시키며 그 애들과 연결된 애들을
계속 push한다 함과 동시에 ans배열에 값을 1로 바꿔준다.

예를들어 input으로

7
0 0 0 1 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 1 1 0
1 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0

이렇게 들어 갔다고 치자 solution(1)을 실행시키면

현재 큐에 나와 연결되어 있는 0,4가 큐에 들어간다.

그후 0,4가 pop 되며 4와 연결되어 있는 4,5와 4,6이 들어간다

이와 동시에 ans[0][5]와 ans[0][6]의 값을 1로 바꿔준다.

그후 다시 4,5를 pop하면서

5,1을 큐에 넣어준다 그후 ans[0][1]을 1로 바꿔준다

그후 4,6을 pop한다

그후 6,7을 푸쉬하면서 ans[0][7]을 1로 바꿔준다

이러한 방식을 반복하면서 진행이된다. 

그럼 이런식으로 해당 Vertex와 연결되어 있는 부분을 나타내주는 배열이 만들어진다