<프로그래머스,백준> 사이클 제거, 11266번 단절점

카테고리 없음

<프로그래머스,백준> 사이클 제거, 11266번 단절점

studying develop 2020. 4. 2. 14:46

[https://programmers.co.kr/learn/courses/30/lessons/49188] 문제 링크

<https://blog.naver.com/jh20s/221248815321>

여기를 좀 참고했다.

~~노드를 제거하고, 사이클이 존재를 확인하는 방법을 내가 아는 걸로는 dfs였다. 근데 이건 시간 초과이니까;;~~

~~그래서 disjoint set으로 확인 가능한가 고민해봤는데 내가 생각하는 선에서는 안되는거 같은데~~

[https://jackpot53.tistory.com/92] 아 이분말 보니까, 유니온파인드를 하고나서, 확인할 수 있는게 아니라, 하는 과정에서 확인이 되네;; 음 만드는 과정에서 확인할 수 있다는 생각은 왜 못했지;

그래서 유니온 파인드로 하면 각 노드 없다 치고, 각 노드 없다 칠때마다 유니온 파인드 해야되니까, 5000 * 5000쯤 이겠다. 대신에 밸런스 맞춰야 된다. 명칭이 뭐더라, 두가지 기법.?

그리고 백 엣지 관련된 부분도 있는데, sds에서 문제 풀다 백엣지 나오긴 했는데, 약간 지름길 찾는 느낌이였던거 같은데? 그 문제도 고난도였음(백엣지 아닐수도 명칭은;) 여기서 어쨋든 백엣지는 사이클을 확인할 수 있따함

~~근데 백엣지는 단방향일때 해당하는거 같다. 일단 유니온 파인드로 풀어보자.~~

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include<cstdio>

using namespace std;

int parent[5001];
int level[5001];

int find(int a) {
	if ( parent[a] == a ){
		return a;
	}
	else {
		return parent[a] = find(parent[a]);
	}
}

int uni(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) {
		return 0;
	}

	if (level[a] > level[b])
	{
		int tmp;
		tmp = a;
		a = b;
		b = tmp;
	}

	parent[a] = b;

	if (level[a] == level[b])
		level[b]++;

	return 1;
}

int solution(int n, vector<vector<int>> edges) {
	int answer = 0;

	for (int i = 0; i < 5000; i++) {
		parent[i] = i;
		level[i] = 0;
	}

	int ans;

	for (int j = 1; j <= n; j++) {
		for (int i = 0; i < 5000; i++) {
			parent[i] = i;
			level[i] = 0;
		}


		for (int i = 0; i < edges.size(); i++) {
			int a, b;
			a = edges[i][0];
			b = edges[i][1];
			if (a == j || b == j) {
				continue;
			}
			else {
				if (uni(a, b)) {
					//printf("%d,%d\n", a, b);
					ans = j;
				}
				else {
					ans = 0;
					break;
				}
			}
		}
		//printf("ans: %d\n", ans);
		answer += ans;
	}

	return answer;
}

이 코드는 시간이 문제다..... [https://blog.naver.com/jh20s/221248815321]

그래프 문제를 풀다 보면 '사이클을 찾아라', '사이클일 경우는 안된다' 라는 조건이 걸린 문제를 종종 볼 수 있습니다.
만약 모든 정점에 대해서 dfs를 돌려 사이클을 찾게된다면 O(V(V+E))라는 시간으로 상당한 시간이 걸리게 될겁니다.
사이클 여부는 DFS트리 한번으로 찾을 수 있습니다.

결론부터 얘기하자면 사이클은 back_edge가 존재할 때 생기고, 이 back_edge의 유무를 찾아주면 됩니다.

단방향 그래프에서 사이클을 어떻게 찾는지 알아보겠습니다.

[출처] 사이클 찾기|작성자 jh20s

나도 결국 저렇게 됐음 시간 복잡도가. 될거 같았는데 10^9 조금 넘어가서 안되는거 같다.

정확성  테스트
테스트 1 〉	통과 (0.03ms, 3.78MB)
테스트 2 〉	통과 (0.03ms, 3.91MB)
테스트 3 〉	통과 (0.03ms, 3.92MB)
테스트 4 〉	통과 (0.07ms, 3.83MB)
테스트 5 〉	통과 (0.03ms, 3.9MB)
테스트 6 〉	통과 (161.34ms, 4MB)
테스트 7 〉	통과 (161.06ms, 4.09MB)
테스트 8 〉	통과 (157.09ms, 3.97MB)
테스트 9 〉	통과 (161.24ms, 4.02MB)
테스트 10 〉	통과 (161.60ms, 4MB)
테스트 11 〉	통과 (0.03ms, 3.86MB)
테스트 12 〉	통과 (0.03ms, 3.95MB)
테스트 13 〉	통과 (0.03ms, 3.95MB)
테스트 14 〉	통과 (0.03ms, 3.86MB)
테스트 15 〉	통과 (0.03ms, 3.79MB)
테스트 16 〉	통과 (130.58ms, 3.98MB)
테스트 17 〉	통과 (403.06ms, 4.11MB)
테스트 18 〉	통과 (381.55ms, 3.96MB)
테스트 19 〉	통과 (4.92ms, 4.03MB)
테스트 20 〉	통과 (5.15ms, 4.02MB)
효율성  테스트
테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)

음 다른 문제 선인장 문제를 좀 보고 고민했는데, 좀 다른게 선인장 문제는 사이클의 갯수를 세는거고 나는 articulation point?...?맞나, 교차점을 찾는것임; [https://www.acmicpc.net/problem/10891]

음 사실 정확히 뭘 찾는건지 모르겠다. 해당 노드가 없으면 사이클이 안만들어지는 조건인데,

그럼 일단 원칙대로는, 한개씩 못간다 하고, dfs로 방문 순서 체크하면서 ? 음 뭘로 체크하지, visit은 안된다. 그건 그냥 안가야 되는곳이 방문했떤곳이라.

음 어떻게 다시온건지 체크하지? 직전에 말고 예전에 방문했떤 곳이면 사이클이 생겼다는 거지.

일단 포기했는데, 내가 모르던 개념을 좀 사용해야 한다.

bcc는 참고

백엣지~!

dfs number 낼 아침ㅇ ㅔ찾아본다.

위에 풀이는 일단 좀 그래프적으로 많이 돌려져 있다.

검색해서 알게된 풀이가 두개 있는데, 일단 노드 갯수가 n개면 간선이 n-1개여야 사이클이 없다.

[https://blog.naver.com/PostView.nhn?blogId=dsyun96&logNo=221860676177&from=search&redirect=Log&widgetTypeCall=true&directAccess=false] 여기서 참고한거다. 근데 간선이 n-1이여도 지운 노드가 단절점이라면 안됨.

그리고 다른 방법은 백 엣지. 일단 다른 글에서 그래프에 대해 좀 더 공부하고 다시 오겠다.

찾아봤는데, 백엣지는 어떻게 활용해야 되는지 모르겠고, 내가 아는 선에서는 무향 그래프의 성질을 이용하는게 맞는거 같다.

즈우북(39.7)

무향 그래프는 각 컴포넌트 단위로 놓고 봤을 때 (엣지 개수) >= (노드 개수)면 무조건 싸이클이 있고 아니면 무조건 없으니까 이 성질을 잘 이용하시면 됩니다

2019.07.27 11:15:07

삭제
- ㅇㅇ(125.143)
  
  감사합니다!!!
  
  2019.07.27 11:20:49
  
  삭제
- ㅇㅇ(125.143)
  
  >는 글자가깨졌는데 엣지 개수가 노드 개수보다 크거나같다로 이해하겠습니다!

음 결국에 일단 내가 부족한 파트는, 무향 그래프임의 성질을 이용 못한거랑, 단절점을 어떻게 구하는지 모르겠다. 찾아 풀자.

단절점의 성질을 어떻게 이용하는지는 일단 알겠다.

#define _CRT_SECURE_NO_WARNINGS
#define NUM 100002
#include<utility>
#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<pair<int, int>> edges;
vector<int> adj[NUM];
int order[NUM];
int arti[NUM];
int root = 1;
//이게 첨에 1부터 되야지,,order를 0으로 초기화했잔아...
int number = 0;

int dfs(int u) {
	//prev는 해당 노드 이후로 가장 작은 순서
	//ret는 현재 노드와 prev중 더 작은거.
	int ret,prev,child=0;
	//order[u]에 값도 잘못넣음, depth로 넣었었따;;
	order[u] = ++number;
	ret = order[u];

	for (int i = 0; i < adj[u].size(); i++) {
		int v = adj[u][i];

		//v는 방문 했었음.갈필요 없네.
		if (order[v] != 0) {
			//여기도 order[v]대신 order[u]로 했었다.
			ret = ret < order[v] ? ret : order[v];
			continue;
		}

		//v는 아직 방문하지 않음.
		prev = dfs(v);
		child++;

		//여기서 틀림,order[u] 대신 ret씀
		if (root != u && prev >= order[u]) {
			arti[u] = 1;
		}

		ret = prev < ret ? prev : ret;
	}

	if (root == u) {
		arti[u] = (child >= 2);
	}

	return ret;
}

int solution(int n, vector<vector<int>> edges) {
	int answer = 0;

	for (int i = 0; i < edges.size(); i++) {
		int a, b;
		a = edges[i][0];
		b = edges[i][1];

		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	for (int i = 1; i <= n; i++) {
		root = i;
		if (!order[i])
			dfs(i);
	}

	int edge_total = edges.size();
	int node_total = n;

	for (int i = 1; i <= n; i++) {
		int edge_num = adj[i].size();
		int comp_num = 0;
		
		if (arti[i]) {
			comp_num = edge_num;
		}
		else {
			comp_num = 1;
		}
		int cnt = 0;
		cnt = (node_total - 1) - (edge_total - edge_num) - (comp_num - 1);
		/*
		cout << "node_total : " << node_total << "\n";
		cout << "edge_num : " << edge_num << "\n";
		cout << "comp_num : " << comp_num << "\n";
		*/

		if (cnt == 1) {
			cout << i << ": " << cnt << "\n";
			answer += i;
		}
	}

	return answer;
}

음 실패했다. 단절점을 제거할때, 노드,간선 갯수가 어떻게 되어야 사이클이 없다 할 수 있는지 다시 해봐야 겠다.

11266번 단절점 [https://www.acmicpc.net/problem/11266] 일단 이거하자.

혼자 고민하다, 생각해도 방문 지점에 순번을 매기고, 현재 보다 더 빠른 순번으로 방문해야 한다는 사실은 이해가 갔는데, 어떻게 흐름이 흘러가는지는 이해가 안됐었다 ,하지만 dfs임을 생각하니까 들어갔다 나오는 흐름을 생각하니 좀 풀렸음. 그래도 몇가지 빠뜨린 부분들이 있어서 [https://www.crocus.co.kr/1164] 참고해서 빨리 고쳤다.

일단 기본 원리가 dfs라고 알고 그걸 틀로 푼다는걸 알아야 이해할 수 있는거 같다.

#define _CRT_SECURE_NO_WARNINGS
#define NUM 10002
#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> adj[NUM];
int order[NUM];
int arti[NUM];
int root = 1;
//이게 첨에 1부터 되야지,,order를 0으로 초기화했잔아...
int number = 0;

int dfs(int u) {
	//prev는 해당 노드 이후로 가장 작은 순서
	//ret는 현재 노드와 prev중 더 작은거.
	int ret,prev,child=0;
	//order[u]에 값도 잘못넣음, depth로 넣었었따;;
	order[u] = ++number;
	ret = order[u];

	for (int i = 0; i < adj[u].size(); i++) {
		int v = adj[u][i];

		//v는 방문 했었음.갈필요 없네.
		if (order[v] != 0) {
			//여기도 order[v]대신 order[u]로 했었다.
			ret = ret < order[v] ? ret : order[v];
			continue;
		}

		//v는 아직 방문하지 않음.
		prev = dfs(v);
		child++;

		//여기서 틀림,order[u] 대신 ret씀
		if (root != u && prev >= order[u]) {
			arti[u] = 1;
		}

		ret = prev < ret ? prev : ret;
	}

	if (root == u) {
		arti[u] = (child >= 2);
	}

	return ret;
}
int N, M;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	freopen("input.txt", "r", stdin);

	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int a,b;
		cin >> a >>b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	//이걸 왜 모든 노드를 루트로 하지?
	//이래야 단절된 지점들에 대해 가능할듯.
	for (int i = 1; i <= N; i++) {
		if (!order[i]) {
			root = i;
			dfs(i);
		}
	}

	int cnt = 0;
	for (int i = 1; i <= N; i++) {
		if (arti[i] == 1) {
			cnt++;
		}
	}
	cout << cnt << "\n";
	for (int i = 1; i <= N; i++) {
		if (arti[i] == 1)
		{
			cout << i << " ";
		}
	}
	cout << "\n";

	return 0;
}

		//(전체 간선의 수) - (i번 정점에 연결된 간선의 수) + (추가로 만들어지는 컴포넌트의 수) < (전체 정점의 수) - 1
		//추가로 만들어 지는 컴포넌트 수가 틀렸다.
		if (edge_total - edge_num + comp_num - 1 < node_total - 1) {
			//cout << i << ": " << cnt << "\n";
			answer += i;
		}

[https://ideone.com/bhTfJu] [https://blog.naver.com/PostView.nhn?blogId=dsyun96&logNo=221860676177&from=search&redirect=Log&widgetTypeCall=true&directAccess=false]

다시 참고해 보자.

음 다시 고민해봤다. 포워드 엣지랑, 백워드 엣지의 의미를 생각해봤다. 특정 노드를 삭제했을때, 모든 노드에서 포워드 엣지만 있거나, 그렇지 않다면 백워드 엣지가 1개만 있어야 한다.

근데 이 방법은, 모든 각 노드에 대해 포워드,백워드 엣지에 대한 갯수 검사가 필요하니까, 일일이 각 엣지를 보며 삭제된 노드에 대한 처리를 해줘야 되서,결국 시간 복잡도는 엣지수*엣지수 일텐데 이러면 시간 초과다. 다시 생각해보자..;;

아니면 도저히 모르겠으면 산만한 고양이 문제 14866번을 먼저 하자.... [https://www.acmicpc.net/problem/14866]

음 그니까 두개 방법이 보이는데, 일단 단절점 방법을 내가 사용 못하는 이유가, 분할 되는 컴포넌트 수를 못구하고 있다....

그래프 그리면서 생각해보니, 백엣지의 나가는 노드가 단절점인데, 단절점에서 forward 엣지 수가 component 수와 같은거 같다.

그래서 component수 구해서 하니까 70점 맞았다.... 음 왜 틀렸지

#define _CRT_SECURE_NO_WARNINGS
#define NUM 100002
#include<utility>
#include <string>
#include <vector>
#include <iostream>

using namespace std;

enum {
	Forward = 1,
	BackWard = 2
};

int forward_edge[NUM] = { 0 };
int backward_edge[NUM] = { 0 };

vector<int> adj[NUM];
int order[NUM];
int arti[NUM];
int root = 1;
//이게 첨에 1부터 되야지,,order를 0으로 초기화했잔아...
int number = 0;

int dfs(int u) {
	//prev는 해당 노드 이후로 가장 작은 순서
	//ret는 현재 노드와 prev중 더 작은거.
	int ret, prev, child = 0;
	//order[u]에 값도 잘못넣음, depth로 넣었었따;;
	order[u] = ++number;
	ret = order[u];

	for (int i = 0; i < adj[u].size(); i++) {
		int v = adj[u][i];

		//v는 방문 했었음.갈필요 없네.
		if (order[v] != 0) {
			//u->v인데, v가 이전에 방문된 지점이라, u->v가 백엣지다.
			backward_edge[u] += 1;
			backward_edge[v] += 1;

			//여기도 order[v]대신 order[u]로 했었다.
			ret = ret < order[v] ? ret : order[v];
			continue;
		}
		else {
			forward_edge[u] += 1;
			forward_edge[v] += 1;
		}

		//v는 아직 방문하지 않음.
		prev = dfs(v);
		child++;

		//여기서 틀림,order[u] 대신 ret씀
		if (root != u && prev >= order[u]) {
			arti[u] = 1;
		}

		ret = prev < ret ? prev : ret;
	}

	if (root == u) {
		arti[u] = (child >= 2);
	}

	return ret;
}

int solution(int n, vector<vector<int>> edges) {
	int answer = 0;

	for (int i = 0; i < edges.size(); i++) {
		int a, b;
		a = edges[i][0];
		b = edges[i][1];

		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	for (int i = 1; i <= n; i++) {
		root = i;
		if (!order[i])
			dfs(i);
	}

	int edge_total = edges.size();
	int node_total = n;

	for (int i = 1; i <= n; i++) {
		int edge_num = adj[i].size();
		int comp_num = 0;

		if (arti[i]) {
			comp_num = forward_edge[i];
		}
		else {
			comp_num = 1;
		}
		
		if ( (node_total - 1) == (edge_total - edge_num) + comp_num) {
			//cout << i << ": " << cnt << "\n";
			answer += i;
		}
	}

	return answer;
}

[https://blog.naver.com/PostView.nhn?blogId=dsyun96&logNo=221860676177&from=search&redirect=Log&widgetTypeCall=true&directAccess=false] 이걸로 하려한건데

if((edge_total - edge_num) + comp_num -1  < node_total - 1 ){
			//cout << i << ": " << cnt << "\n";
			answer += i;
		}

이게 왜 틀리지 어느 부분이 문제인지 모르겠따;; forward랑 backward 구할때 틀렸을 수 도 있다.

사이클 문제 더 풀어볼거... [https://blog.naver.com/jh20s/221248815321] 여기서 올려준거 괜찬은거 같다.

도저히 모르겠어서 해답을 봤다.... 내일 나랑 뭐가 다른지 다시 생각해 보겠다.

#include <vector>
#define N 5001
using namespace std;

int c[N], d[N], n, m, k;
vector<int> e[N];
pair<int, int> dfs(int i, int p) {
    int a=0, b=0, f=0;
    bool ok=true;
    d[i]=d[p]+1;
    for(int j : e[i]) if(j!=p) {
        if(!d[j]) {
            auto[x, y]=dfs(j, i);
            ok&=x==0 && y<2;
            a+=x, b+=y;
        }
        else if(d[j]<d[i])
            b++, f++, c[j]++;
    }
    if((ok || (a==0 && b-f-c[i]<2)) && a+b==m-n+1)
        k+=i;
    return {a+c[i], b-c[i]};
}
int solution(int nodes, vector<vector<int>> edges) {
    n=nodes; m=edges.size();
    for(const auto& x : edges)
        e[x[0]].push_back(x[1]),
        e[x[1]].push_back(x[0]);
    dfs(1, 1);
    return k;
}

현재글<프로그래머스,백준> 사이클 제거, 11266번 단절점

swift, python, java, 아이폰 앱 개발, 안드로이드 앱 개발, 서버 공부, 머신러닝 공부, 그래픽스 공부 등등 기록입니다.

IOS, Django, application.properties, 파이썬, 프로그래머스, present, URLSessionTask, node.js, 안드로이드, 함수형 프로그래밍, 스프링부트, 백준, SWIFT, 릿코드, leetcode, watchConnectivity, 면접 대비, 알고리즘, 스위프트, 스택,

Today :
Yesterday :

개인적으로 공부한 내용을 정리중입니다.

<프로그래머스,백준> 사이클 제거, 11266번 단절점

'카테고리 없음'의 다른글

티스토리툴바

« 2024/05 »
일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31