네트워크(V)

▶문제 https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

 

컴포넌트 문제로 bfs로직 생각나지 않아서 dfs형식으로 풀음.

 

 

▶문제 설명:

네트워크의 갯수를 세는 문제로 네트워크 안에는 컴퓨터들이 이루어져 있다. 이중 벡터로 주어진 computers 변수 안에 컴퓨터들간 연결을 표시하는 1의 값이, 연결을 표시하지 않는 0의 값이 들어있다. 이를 활용해 연결된 컴퓨터들의 네트워크 갯수를 구하는 문제이다. 

 

   A  B  C  D

A 1  0  1   0

B 0  1  0   0

C 1  0  1   1

D 0  0   1  1

이처럼 2차원 배열이 있으면 A - C - D  , B

로 Component가 구성되어있다. A와 C가 연결되있고 C와 D가 연결되 있으면 A와 D가 연결되 있는 것이다.

 

▶로직

1. used 라는 방문 체크 용도로 배열을 201사이즈로 만든다(컴퓨터 갯수 1~200 이하인 자연수)

2. for문을 통해 주어진 컴퓨터 갯수 만큼 행을 탐색하여 탐색하지 않은 곳에 used[인덱스] = 1 로 체크한다. 재귀를 통해 해당 행의 연결된 컴퓨터를 탐색하도록 열에 접근한다.

3. 이미 방문했던 컴퓨터는 used[x] == 0 을 조건으로 재귀를 돌리지 않는다.

4. 방문하지 않은 열(x)의 컴퓨터를 행으로 재귀함수의 input(y)값으로 설정한다.

5. 재귀 함수가 완전히 빠져나오면 counting 갯수를 하나 올린다.

6. 연결된 컴퓨터들은 더 이상 방문을 하지 않으며,  위 로직을 computers 사이즈까지 반복한다. 

 

#include <string>
#include <vector>

using namespace std;
int used[201]; // 방문 여부

void recursion(int dy, vector<vector<int>> computers){
    for(int dx = 0; dx < computers.size(); ++dx){ // 열탐색
        if(computers[dy][dx] == 1 && used[dx] == 0){ //연결 여부, 방문여부 체크
            used[dx] = 1; // 방문 체크
            recursion(dx, computers); // 재귀
        }
    }
    return;
}
int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    for(int y = 0; y< computers.size();++y){ // 행 접근
        if(used[y] == 0){ // 해당 행 컴퓨터에 접근 하지 않았으면
            used[y]= 1;  // 접근표시
            recursion(y, computers); // 열 탐색 및 연결된 컴퓨터의 행에 접근 목적 재귀활용.
            answer++; // counting
        }
    }
    return answer;
}

---

섬 bfs로 품( 잘못접근)

/*
* 
* 방향 배열 통해 bfs 접근
used [200][200]  used 체크 중복 방문x
*/
#include<iostream>
#include<vector>

using namespace std;

struct node {
	int y;
	int x;
};
int used[201][201];
int directArray[4][2]{ -1,0,0,1,1,0,0,-1 };
void bfs(int ry, int rx, vector<vector<int>> computers) {
	int n = computers.size();
	int head = 0;
	int tail = 1;
	node queue[201] = { 0,0 };
	queue[0] = { ry,rx };

	while (head != tail) {
		node now = queue[head++];
		for (int y = 0; y < 4; ++y) {
			int dy = directArray[y][0] + now.y;
			int dx = directArray[y][1] + now.x;
			if (dy < 0 || dx < 0 || dy >= n || dx >= n)continue;
			if (used[dy][dx] == 1)continue;
			if (computers[dy][dx] == 0)continue;
			used[dy][dx] = 1;
			queue[tail++] = { dy,dx };
		}
	}
}
int solution(int n, vector<vector<int>> computers) {
	int answer = 0;
	for (int y = 0; y < computers.size(); ++y) {
		for (int x = 0; x < computers.size(); ++x) {
			if (used[y][x] == 1 || computers[y][x] == 0)continue;
			used[y][x] = 1;
			bfs(y, x, computers);
			answer++;
		}
	}
	cout << answer << endl;
	return answer;
}
int main(void) {
	solution(4, { {1,0,1, 0},{0,1,0, 0},{1,0,1,0},{0,0,0,1 } });
}