[BOJ] [C++] 25195 Yes or yes

25195번: Yes or yes

매일매일은 아니어도 조금씩은 풀어야 할 것 같아서 풀어보게 되었다.

백준 허브라는 확장 플러그인이 있는데, 이걸 적용하면 백준 문제를 풀었을 때 깃에 바로 커밋이 된다.

어제 백준 허브도 설정해 놨고 신나서 몇 문제 조금 풀었다!!

 

GitHub - lyh109/Algorithm: This is a auto push repository for Baekjoon Online Judge created with [BaekjoonHub](https://github.co

최근에 DFS 강의를 봤고, DFS 문제를 몇 문제 풀어보고 있다. 얼른 다른 강의도 보고 공부해서 여러 문제들을 풀어보고 싶다. 오랜만에 문제를 푸니 재미있다 ㅎ.ㅎ

 

풀이 과정

투어리스트 곰곰이가 그래프 위에서 여행을 하는데, 여행 중 팬클럽 곰곰이를 만나지 않는 경로가 있는지를 판별하는 문제다.

어떻게 이동하든 팬클럽 곰곰이를 만나야 하면 Yes, 만나지 않고 이동할 수 있는 방법이 있다면 yes를 출력해야 한다!

 

그래프는 DAG(Directed Acyclic Graph)이다. 방향성이 있는 비순환 그래프라는 뜻이다.

특정 노드에서 자기 자신으로 돌아오는 경로, 즉 사이클이 없다.

새벽에 한 문제만 더..! 하고 풀다가 문제를 정확하게 못 읽어서 이 부분을 놓쳤다 ㅜㅜ..

문제를 꼼꼼히 읽는 습관을 들일 것!!

 

for (int i = 0; i < M; ++i)
{
	int s, e;
	cin >> s >> e;

	A[s - 1].push_back(e - 1);	
}

방향성이 있는 그래프이므로~ 양쪽을 연결하지 않고 입력으로 주어지는 대로 정점 데이터를 벡터에 넣어주었다.

 

if (!meet || find(gomgom.begin(), gomgom.end(), pos) != gomgom.end())
{
	return;
}

if (A[pos].size() == 0)
{
	meet = false;
	return;
}

검사를 마치는 조건

• 팬클럽 곰곰이를 만나는 순간에 그 경로는 팬클럽 곰곰이를 만나야 하는 경로로 결정되었으므로, 검사를 더 수행할 필요가 없다.
• 팬클럽 곰곰이를 만나지 않는 경로를 찾았다면, yes를 출력하면 되므로 검사를 더 수행할 필요가 없다.
• 경로의 시작 지점에서 끝까지 도착하였는데 팬클럽 곰곰이를 만나지 않고 도착했다면! 팬클럽 곰곰이를 만나지 않는 경로를 찾은 것이므로 쭈우욱 리턴해준다!

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

static vector<vector<int>> A;
static vector<int> gomgom;
static bool meet = true;

void DFS(int pos);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N, M;
	cin >> N >> M;

	A.resize(N);

	for (int i = 0; i < M; ++i)
	{
		int s, e;
		cin >> s >> e;

		A[s - 1].push_back(e - 1);
	}

	int s;
	cin >> s;
	gomgom.resize(s);

	for (int i = 0; i < s; ++i)
	{
		int gom;
		cin >> gom;
		gomgom[i] = gom - 1;
	}

	DFS(0);

	if(meet) cout << "Yes" << '\n';
	else cout << "yes" << '\n';

	return 0;
}

void DFS(int pos)
{
	if (!meet || find(gomgom.begin(), gomgom.end(), pos) != gomgom.end())
	{
		return;
	}

	if (A[pos].size() == 0)
	{
		meet = false;
		return;
	}

	for (int i : A[pos])
	{
		DFS(i);
	}
}

 

학교 다닐 때는 공부하거나 이렇게 문제를 풀고 나서 그냥 끝~ 이었는데, 복기 겸 기록 용도로 이렇게 글을 쓰는 것도 좋은 것 같다. 학교 다닐 땐 왜 이런 걸 할 생각을 못했나 몰라!! 학교 다니면서 수업 내용을 엄청 타이핑 해놓고 나만 봤는데, 시간이 나면 그 내용들도 천천히 블로그에 포스팅하고 싶다! 급하게 따라 치느라 구어체여서 정리는 한 번 해야 할 것 같지만 ㅎ.ㅎ,,

혼자 보고 지우기에는 아까운 자료들이어서 친구들한테 공유를 해주고는 있지만! 나도 다시 공부하면 좋을 내용들이고 하니 다시 정리해보는 것으로!!