[11403] 경로 찾기, c++

[11403] 경로 찾기

 

www.acmicpc.net/problem/11403

11403번: 경로 찾기

막간을 이용해 풀었던 마지막 문제

이것도 진짜 기본적인 그래프 문제처럼 보인다. 함정이 있었음 ㅋㄷ

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int arr[101][101]={0};
int n;
void bfs(int start){
	queue<int> q;
	int visit[101]={0};
	q.push(start);
	while(!q.empty()){
		int x = q.front();
		q.pop();
		for(int i=0; i<n; i++){
			if(!visit[i] && arr[x][i]==1){
				q.push(i);
				visit[i] = 1;
				arr[start][i] = 1;
			}
		}
	}
}
int main(){
	cin >> n;
	int m;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			scanf("%d", &m);
			if(m==1){
				arr[i][j] = 1;
			}
		}
	}
	for(int i=0; i<n; i++){
		bfs(i);
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			printf("%d ", arr[i][j]);
			if(j==n-1)	printf("\n");
		}
	}
}

그냥 입력 받는 대로 인접행렬 만들어주고, 정점마다 bfs 돌려서 연결 되는 곳은 인접행렬을 1로 바꿔주면 된다. 계속 답이 이상하게 나왔는데 자세히 보니 자기 자신한테 다시 돌아올 수 있는 경우가 체크가 안되고 있었다.

어떻게 할 까 생각해봤는데 그냥 처음에 bfs 돌렸을 때 바로 visit배열을 1로 바꿔주면 안되는 거였음.

즉 visit[start] = 1; 을 하면 안됨! => 자기 자신, 즉 1->1로 가는 경우를 생각하지 않아버림.

무튼 다른사람은 다 생각했을 지라도 난 이거 생각 못하다 고쳤음 ㅋㄷ

위에 두 문제보다는 쉬운 그래프 문제