[C++]Softeer/HSAT Level3 - 출퇴근길

<문제>

https://softeer.ai/practice/info.do?idx=1&eid=1529 

Softeer

자동차로 출퇴근을 하는 동환이는 지루하지 않게 종종 길을 바꿔 다니곤 한다. 새로운 동네를 발견하는 일은 동환이의 소소한 행복이다.동환이의 출근길과 퇴근길은 가끔 겹친다. 즉, 출근길에 들른 동네를 퇴근길에 다시 지나곤 하는 것이다. 이에 대해 곰곰이 생각하던 동환이는 이렇게 두 번 들를 수 있는 동네가 그렇게 많지 않음을 깨달았다. 도로의 연결 모양, 그리고 일방통행 여부 등으로 인해 출퇴근길 모두 방문 가능한 동네가 한정되는 것이다.동환이의 출퇴근길은 단방향 그래프로 나타낼 수 있다. 즉, 각 동네를 1부터 n까지의 번호가 매겨진 n개의 정점으로, m개의 일방통행의 도로를 단방향 간선으로 삼아 그래프를 만들 수 있다. 이때 동환이의 집과 회사가 각각 정점 S와 T로 나타난다고 하면 출퇴근길은 S와 T 사이의 경로로 나타난다.동환이의 출퇴근길을 본딴 그래프가 주어지면 S에서 T로 가는 출근길 경로와 T에서 S로 가는 퇴근길 경로에 모두 포함될 수 있는 정점의 개수를 세는 프로그램을 작성하시오.단, 출퇴근길에서 목적지 정점을 방문하고 나면 동환이는 더 이상 움직이지 않는다. 즉, 출근길 경로에 T는 마지막에 정확히 한 번만 등장하며, 퇴근길 경로도 마찬가지로 S는 마지막에 한 번만 등장해야 한다. (출근길 경로에 S는 여러 번 등장해도 되고, 퇴근길 경로에 T는 여러 번 등장해도 된다.)

제약조건
* 5 ≤ n ≤ 100,000
* 5 ≤ m ≤ 200,000
* 1 ≤ S ≤ n이고 1 ≤ T ≤ n이며 S ≠ T
* S에서 T로 가는 경로와 T에서 S로 가는 경로가 하나 이상 존재함이 보장된다.
* 간선의 양 끝 점은 서로 다르다.
* 같은 정점쌍을 같은 방향으로 잇는 간선은 두 개 이상 주어지지 않는다.

<제출답안>

#include<iostream>
#include<vector>

using namespace std;

int answer = 0;
vector<int> adj[100100];
vector<int> adjR[100100];
bool FromS[100100];
bool FromT[100100];
bool ToS[100100];
bool ToT[100100];

void dfs(int now_idx, bool visit[])
{
	
	if(visit[now_idx] == 1)	
		return;
	visit[now_idx] = 1;

	for(int k=0;k<adj[now_idx].size();k++)
	{
		int new_idx = (int)(adj[now_idx][k]);
		dfs(new_idx, visit);
	}
	return;
}

void dfsR(int now_idx, bool visit[])
{
	if(visit[now_idx] == 1)	
		return;
	visit[now_idx] = 1;

	for(int k=0;k<adjR[now_idx].size();k++)
	{
		int new_idx = (int)(adjR[now_idx][k]);
		dfsR(new_idx, visit);
	}
	return;
}


int main(int argc, char** argv)
{
	int n,m;
	cin>>n>>m;

	for(int i=0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		adj[x].push_back(y);
		adjR[y].push_back(x);
	}

	int s,t;
	cin>>s>>t;

	FromS[t] = 1;
	dfs(s, FromS);

	FromT[s] = 1;
	dfs(t, FromT);

	dfsR(s, ToS);

	dfsR(t, ToT);

	for(int j=1;j<n+1;j++)
	{
		if(FromS[j]&&FromT[j]&&ToS[j]&&ToT[j])
		{
			answer++;
		}
	}

	//출발점과 끝점은 제외해주기
	cout<<answer-2<<endl;
	return 0;
}

구현 방법은 아래 유튜브를 참조하였다.

https://www.youtube.com/watch?v=PAihI2CGr-M

adj와 adjR을 구하는 이유는

adj에서   s : 출근길 시작, t : 퇴근길 시작

adjR에서 s: 퇴근길 도착, t : 출근길 도착

의 개념으로 4개 모두에 해당이 되어야 출근길에 있으면서 퇴근길에도 있는 길이기 때문이다.

 

python 처럼 간단히 구현이 어려워서 dfs, dfsR 이라는 함수 2개를 이용했는데,

이렇게 되면서 adjR 자리에 adj를 넣는 실수 한번, dfsR에서 dfsR을 다시 호출해야하는데 그냥 dfs를 호출해버리는 실수 한번으로 꽤 많은 실패 끝에 맞았습니다! 를 얻어냈다...

 

다음부터는 dfs, dfsR 이런식으로 두개의 함수 말고 하나의 함수로 통일해서 인자를 추가해주는게 나을거같다.

이래야 내가 모르는 구멍에 빠지지 않을테니;;

나중에 시간이 된다면 한개의 함수로 구현한 코드를 찾아서 올려보도록 하겠다! ㅎㅎ

 

---> 다음은 하나의 함수로 통일한 코드이다.

#include<iostream>
#include<vector>

using namespace std;

#define ADJ  0
#define ADJR 1

int answer = 0;
vector<int> adj[100100];
vector<int> adjR[100100];
bool FromS[100100];
bool FromT[100100];
bool ToS[100100];
bool ToT[100100];

void dfs(int now_idx, bool visit[], int direction)
{
	
	if(visit[now_idx] == 1)	
		return;
	visit[now_idx] = 1;

	if(direction == ADJ)
	{
		for(int k=0;k<adj[now_idx].size();k++)
		{
			int new_idx = (int)(adj[now_idx][k]);
			dfs(new_idx, visit, direction);
		}
	}
	else if(direction == ADJR)
	{
		for(int k=0;k<adjR[now_idx].size();k++)
		{
			int new_idx = (int)(adjR[now_idx][k]);
			dfs(new_idx, visit, direction);
		}

	}
	return;
}

int main(int argc, char** argv)
{
	int n,m;
	cin>>n>>m;

	for(int i=0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		adj[x].push_back(y);
		adjR[y].push_back(x);
	}

	int s,t;
	cin>>s>>t;

	FromS[t] = 1;
	dfs(s, FromS, ADJ);

	FromT[s] = 1;
	dfs(t, FromT, ADJ);

	dfs(s, ToS, ADJR);

	dfs(t, ToT, ADJR);

	for(int j=1;j<n+1;j++)
	{
		if(FromS[j]&&FromT[j]&&ToS[j]&&ToT[j])
		{
			answer++;
		}
	}

	//출발점과 끝점은 제외해주기
	cout<<answer-2<<endl;
	return 0;
}

기억할 점은 1) 도착후에 더 진전되면 안되니까 FromS[t] 와 FromT[s]를 1로 set해주기

2) 출발점과 도착점은 갯수에서 빼주기!