[Softeer] 출퇴근길 with C++(HSAT 6회 기출)

https://softeer.ai/practice/6248

Softeer - 현대자동차그룹 SW인재확보플랫폼

언어: C++, 소요시간: 153 ms  

 

내 혼자 힘으로 못 풀고 친구꺼 참고했다.

이걸 어떻게 생각해내는거지??? ㅠㅠㅠ

 

문제 핵심

집 -> 회사로 가는 경로, 회사 -> 집 가는 경로에서 공통되는 노드 개수 찾기.

집과 회사는 무조건 그래프를 타고 갈 수 있음이 보장됨.

출발 노드는 재방문이 가능하지만, 도착노드는 재방문이 불가능하다. 

 

문제해결

모든 노드에서 방문할 수 있는 경우의 수를 확인할 수도 있지만, 그러면 시간초과난다.

따라서 dfs를 총 4번 돌리며 확인해서 해결한다.

 

visited1. 출근길: 집에서 어딘가로

집 -> 방문할 수 있는 모든 노드를 visited1에 체크한다. 이때 회사에 도착하면 다른 노드 방문 x, 미리 visited한다.

 

visited 2. 퇴근길: 회사에서 어딘가로

회사 -> 방문할 수 있는 모든 노드를 visited1에 체크한다. 이때 회사에 도착하면 다른 노드 방문 x, 미리 visited한다.

 

이때, 어딘가 노드에서 집 or 회사 로 갈 수 있는지 확실하게 알 수 있는 방법이 없다.

-> 간선 방향을 역방향으로 만든 역방향 그래프를 사용하면 된다!!! 나는 reverseV라고 했다.

 

visited3. 퇴근길: 어딘가에서 집으로 갈 수 있는지 체크 

어딘가서에서 집으로 갈 수 있다면, 역방향 그래프에서 역으로 집 -> 어딘가 노드가 방문 가능하다면 해당 노드에서 집으로 방문할 수 있다는 뜻이 된다! 이때 출발 노드는 다시 재방문이 가능하므로, (이 dfs에선 회사노드 T) 미리 visited하지 않는다.

 

visited4. 출근길: 어딘가에서 회사로 갈 수 있는지 체크 

어딘가서에서 회사로 갈 수 있다면, 역방향 그래프에서 역으로 회사 -> 어딘가 노드가 방문 가능하다면 해당 노드에서 집으로 방문할 수 있다는 뜻이 된다! 이때 출발 노드는 다시 재방문이 가능하므로,  (이 dfs에선 집노드 S)  미리 visited하지 않는다.

 

이후 visited1, visited2, visited3, visited4

이때 출근지점과 

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
using namespace std;

// 정점개수, 간선개수, 출근정점, 퇴근정점, 정답
int N, M, S, T, answer;			
// 출근하면서 갈 수 있는 곳, 퇴근하면서 갈 수 있는 곳, 각 정점에서 S로 갈 수 있는지 여부, 각 정점에서 T로 갈 수 있는지 여부 
int visited1[100001], visited2[100001], visited3[100001], visited4[100001];
vector <int> V[100001], reverseV[100001];

void input() {

	cin >> N >> M;
	
	int start, end;
	for (int i = 0; i < M; i++) {
		cin >> start >> end;
		V[start].push_back(end);
		reverseV[end].push_back(start);
	}
	cin >> S >> T;
}

// S 와 T끼리는 무조건 갈 수 있음이 보장된다.
void dfs(int startNode, vector <int> graph[], int visited[]) {
	
	visited[startNode] = 1;

	for (int target : graph[startNode])	{
		if (visited[target])
			continue;
		else
			dfs(target, graph, visited);
	}
}

int main() {
	//freopen("sample_input.txt", "r", stdin);
	input();

	visited1[T] = 1, visited2[S] = 1;
	dfs(S, V, visited1);
	dfs(T, V, visited2);
	dfs(S, reverseV, visited3);
	dfs(T, reverseV, visited4);
	
	for (int i = 1; i <= N; i++){
		if (visited1[i] && visited2[i] && visited3[i] && visited4[i])
			answer++;
	}
	
	cout << answer - 2;	// 출발, 도착지 빼야함

	return 0;
}