작은시작

문제

https://www.acmicpc.net/problem/11403

풀이

기본 그래프 문제처럼 풀었다. 알고리즘 분류 및 타 블로그에는 플로이드 와샬로 많이 푼 것 같다. 

하지만 기본 DFS 그래프 탐색으로도 풀 수 있을 것 같아서 그렇게 풀었다. 이런 그래프 문제는 2차원 배열 형식으로 풀기보단 Vector를 사용하는 것이 생각하기 좀 더 수월한 것 같다. 

visited배열을 활용하여 기본 Cycle방지 + 인덱스에 값을 할당하였다.

코드

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int N;
vector<int> map[101];
int visited[101];
void dfs(int k) {

	for (int i = 0; i < map[k].size(); i++) {
		if (visited[map[k][i]] == 0) {
			visited[map[k][i]] = 1; //다음칸
			dfs(map[k][i]);
		}
	}

}
int main() {
	cin >> N;
	
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			int a;
			cin >> a;
			if(a==1)map[y].push_back(x);

		}
	}


	for (int i = 0; i < N; i++) {
		memset(visited, 0, sizeof(visited));
		dfs(i);
		
		for (int j = 0; j < N;	j++) {
			cout << visited[j] << " ";
		}
		cout << '\n';
	}

	return 0;
}

https://programmers.co.kr/learn/courses/30/lessons/43162

코드 설명

visited배열을 통해 네트워크가 형성될때마다 표시해줍니다. 재귀를 사용하였고 level로 넘어갈때 그전 i 를 이용하여 네트워크 형성하는지 체크후 재귀하게됩니다. 

기본 그래프 문제이므로 기억이 안난다면 백준 기본문제를 다시 풀어보면 좋을것 같습니다 !! 

(main문에서 항상 dfs는 0 으로 시작한다는 습관 없애자!)

코드 

#include <string>
#include <vector>
#include <iostream>
using namespace std;

bool visited[201];

void dfs(int level,int n,vector<vector<int>> &computers){
    visited[level]=true;
    
    for(int i=0;i<n;i++){
        if(!visited[i] && computers[level][i]==1){
            
            dfs(i,n,computers);
            
        }
    }
    
}

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

    for(int i=0;i<n;i++){
        if(!visited[i]) {
            answer++;
            dfs(i,n,computers);
        }
    }
    
    
    
    
    
    return answer;
}