[Graphs] Graphs- DFS - Number of Provinces

https://leetcode.com/problems/number-of-provinces/

Number of Provinces - LeetCode

 

이번에는 Graph에서 DFS 용으로 예제 문제풀이를 볼려고하는데 만만치가않다. 일단은 무조건 따라해보기! 

 

• 구하고자하는것: Provinces로 그룹을 말하는데 연결된 노드들은 하나의 그룹으로 쳐지고 아무것도 연결되지않은것도 각 그룹으로침. 몇개의 그룹이 있는가?
• 풀이 구조: 인접 리스트 방식
• Time complexity :  바이너리 트리는 child node 가 정해져있기때문에 각 한번씨만 방문하면 되서 O(1) 이 소요되지만 그래프는 이와다르게 for loop를 이용해 각 노드의 neighbor 노드를 방문해야하기때문에 O(nodes + edges) 만큼 소요가 된다.  최악의 시나리오는 모든 노드가 연결되어있을때 n^2만큼 소요가 되나 자세히 말하자면 해쉬맵을 사용할때는 O(n^2)만큼 걸린다고 생각하면되는데 그이유는 adjacency matrix를 인풋으로 하기 때문이라고한다. 

우선 코드를 보면

 

class Solution{
public:
	unordered_map<int, vector<int>> graph; // hashmap을 사용하게 되는것 췤
	vector<bool> seen; // 바이너리 트리와 다르게 그래프는 원형구조가 될 수 있어 체크노드를 표시해놓는 변수
	
	int findCircleNum(vector<vector<int>>& isConnected){
	int n = isConnected.size(); // 노드의갯수
	seen = vector(n,false); //this is needed to prevent a cycle structure.
	for (int i=0; i<n; i++){// n이 3이면 i는 0 ,1,2
		for(int j=i+1;j<n; j++){
			if(isConnected[i][j]  == 1 ) {// ith 와 jth node 가 연결됬다는것
				graph[i].push_back(j);
//graph[i]는 key 부분이 되는것이고 여기에 푸쉬백이 들어가느것은 value 부분으로 생각.
//근데 왜 i 에 j부분이 들어가게 되는것이지?,바꿔봤더니 wrong answer!
//아하! hash 이기 때문에 graph[i] 이미 다이나믹 메모리로 들어가고 i에 j를 넣어주는것은 서로 
//연결되어있기때문에 graph[i].push_back(j); graph[j].push_back(i); 로 채워준다!
				graph[j].push_back(i);
			}
		}
	}
	
	int ans = 0;
	for (int i =0; i < n ; i++){ //노드의 갯수 만큼 순환되면서
		if (!seen[i]){// false는 체크가안된것으로 
			ans++; 
			seen[i] = true;  // checking mark
			dfs(i); 
//여기서 꽤나 중요한 포인트로 binary tree에서는 i 자리에 root가 들어가는데 graph에서는 interger 가 들어가는 알고리즘으로 풀이! 해설에서는 이게 굉장히 중요하다함! 
//머리속에 그려보면...오... 아트
//Argument로 integer가 들어가도 되는이유는 graph가 해쉬맵형태로 키를 입력하면 키에 연결된 노드들이
들어있고 이를 stack을 사용해서 이 노드에 연결된 모든 노드를 체크하는 형식이다. 이래서 DFS 구나...
        }
	}
	
	return ans;
}

	void dfs(int node){ // 이 함수의 역할은 키에 연결된 노드들을 돌아니며 Seen(이미봤어)를 true로
    // 만들어줌으로써 다시 방문할 거리를 주지않기위해. 그래서 위에 ans가 ++ 시키는것을 이해할 수 있다.
		stack<int> stack;
		stack.push(node);
		
		while(!stack.empty()){
			int node =stack.top();
			stack.pop();
			for (int neighbor:graph[node]) {
				if(!seen[neighbor]){
				//next two lines are needed to prevent cycles
					seen[neighbor] = true;
					dfs(neighbor);
				}
			}
		}
	}
};

 

---

알고리즘은 그냥 이해하고 외워야한다. 어렵지만 결국 면접용일뿐이고  알고리즘을 짠 사람들을 그냥 대단하고 경외하면된다. 나도 언젠간 이 허접한 포스트에서 벗어나 요지를 팍팍 파악하며 코딩문제를 푸는날을 상상해본다.

Wrap-up points

• Hash map 을 사용한다 
• seen variable로 방문한것인지 방문하지않을것을 안다
• 문제의 요지를 이해해 ans 구조가 어떤지 구성한다.
• DFS를 사용시 Argument로 integer가 들어감을 이해하고 이는 hash map가 조화됨을 이해한다.