[알고리즘 기 시 뮬 레이 션 문제] 1007. 미니 카.

[문제 설명]
공유 경제가 발전 함 에 따라 대학 도 시 는 현재 곳곳에서 ofo 노 란 차 를 볼 수 있다. 왼쪽 은 현재 매일 노 란 차 를 타고 기숙사 에서 실험실 로 갈 계획 이다. 대학 도시 의 지 도 를 방향 이 있 는 그림 으로 간략화 할 수 있다 고 가정 하면 그림 에 N 개의 장소 (노드) 가 있 고 0 에서 N - 1 로 번 호 를 매 길 계획 이다. 어떤 장소 사이 에 방향 이 있 는 도로 (방향 이 있 음) 가 존재 한다. 왼쪽 의 기숙사 가 있 는 곳 번 호 는 0 이다.실험실 이 있 는 장소 번 호 는 N - 1 입 니 다. 왼쪽 은 연속 적 인 M 일 계획 노선 을 원 합 니 다. 매일 기숙사 에서 실험실 까지 적어도 이전에 가지 않 았 던 길 (방향 이 있 음) 을 지나 갑 니 다. 왼쪽 은 M 의 최대 치 를 알 고 싶 습 니 다. 당신 은 그 를 도와 줄 수 있 습 니까?
 
아래 Solution 클래스 의 countPath 함 수 를 실현 하여 상기 기능 을 완성 하 십시오.
매개 변수 G: N * N (2 < = N < = 50) 인접 행렬, 장소 i 에서 장소 j 사이 에 도로 가 있 으 면 G [i] [j] = 1;그렇지 않 으 면 G [i] [j] = 0. G [i] [i] 의 값 은 항상 0 이다.
반환 값: M 의 최대 값 입 니 다. 요 구 를 만족 시 키 는 경로 가 존재 하지 않 으 면 0 으로 돌아 갑 니 다.
 
class Solution {
public:
int countPaths(vector> G) {
}
         
};
 
예 1:
G = {0, 1}, {1, 0}}, 반환 값 은 2 입 니 다. 왜냐하면 첫날: 0 -- > 1, 다음날 0 -- > 1 --> 0 --> 1. 왼쪽 이 다음날 한 바퀴 돌 았 지만 그 는 첫날 지나 지 않 은 가장 자 리 를 걸 었 다. 1 - > 0.
 
예 2:
G = {0, 1, 1}, {1, 0, 1}, {1, 0, 0}, 반환 값 은 4 입 니 다.
제 1 일: 0 -- > 2
다음날: 0 -- > 2 --> 0 --> 2
제 3 일: 0 -- > 1 --> 2
넷 째 날: 0 -- > 1 --> 0 --> 1 --> 2
 
예 3:
G = {0, 1, 0}, {1, 0, 0}, {0, 0, 0}, 반환 값 은 0 입 니 다.
[문제 풀이 분석]
n 개의 정점 이 있 는 그림 은 노드 0 에서 노드 n - 1 까지 의 경로 의 최대 수 를 구 합 니 다. 그 중에서 모든 경 로 는 이전에 가지 않 았 던 변 을 포함해 야 합 니 다.
우 리 는 이렇게 고려 할 수 있다. 먼저 노드 0 에서 도착 하지 못 하 는 모든 노드 와 이 노드 와 관련 된 변 을 삭제 할 수 있다. 노드 0 이 도착 하지 못 하기 때문에 우리 의 결과 에 아무런 영향 을 주지 않 는 다.그 다음 에 노드 n - 1 노드 에 도달 하지 못 하 는 모든 노드 와 관련 된 부분 을 삭제 하면 우리 의 결과 에 도 영향 을 주지 않 습 니 다.이 노드 와 변 을 삭제 하여 새로운 그림 을 만 들 었 습 니 다. 크기 는 m 개의 노드, k 개의 변 입 니 다.
마지막 으로 우 리 는 한 노드 를 지나 갈 때마다 반드시 두 개의 변 을 소모 해 야 한다. 즉, 한 개의 입 변, 한 개의 출 변 이지 만 우리 의 출발점 과 종점 변 은 필요 하지 않다. 즉, m - 2 개의 노드 이다.그래서 우 리 는 (k - (m - 2) 경 로 를 얻 을 수 있다.
예:
1. 0.....................................................................................
2. 0.....................................................................................
3, 0.................................................................................
[소스 코드]

class Solution {
public:
	int countPaths(vector > G) {
		int result = 0;
		int m = G.size();
		int n = G[0].size();
		if (m < 2 || n < 2 || n > 50 || m > 50)	return 0;
		//        
		vector vis(m,0);
		
		//          
		vector to_des(n,0);
		queue visited;
		
		//            
		visited.push(0);
		vis[0] = true;
		while(!visited.empty()) {
			int t = visited.front();
			visited.pop();
			for (int i = 0; i < m; i++) {
				if(G[t][i] == 1 && !vis[i] && t != i) {
					vis[i] = true;
					visited.push(i);
				}
			}
		}
		if (!vis[n-1])	return 0;
		
		//            
		visited.push(n-1);
		to_des[n-1] = true;
		while(!visited.empty()) {
			int t = visited.front();
			visited.pop();
			for (int i = 0; i < m; i++) {
				if (G[i][t] == 1 && !to_des[i] && i != t) {
					to_des[i] = true;
					visited.push(i);
				}
			}
		}
		
		//       
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (G[i][j] == 1 && vis[i] && vis[j] && to_des[i] && to_des[j]) {
					result++;
				}
			}
		}
		for (int i = 0; i < n; i++) {
			if (to_des[i] && vis[i]) {
				result--;
			}
		}
		return result+2;
	}
};