프로그래머스 43162 - 네트워크
접근 및 생각
사족
- 프로그래머스의 대부분 풀이들은 DFS 방식이였지만, 내가 이 문제를 처음 접근할 때 BFS 방식이 먼저 떠올라서 BFS 방식으로 풀게 되었다.
본론
- BFS에 관한 내용은 (링크)를 참조
- BFS는 큐를 활용하는 탐색 방식으로, 코드로 구현할 때 다음과 같은 요소를 고려하여야 한다.
- queue의 데이터 타입
- queue의 초깃값
- q.front() 원소가 답이 될 수 있는지, 혹은 정보 update가 가능한지 check 이후 행동
- 읽어온 원소로부터 queue에 push할 수 있는 원소를 push 하기
queue의 데이터 타입
- queue가 기억해야 할 것은
computers
의 index 값이므로queue<int> q;
queue의 초깃값
- 일단
computers
의 0번 index부터 탐색할 것이므로q.push(0); visit[0] = answer;
- 그리고
computers
의 index를 탐색했는 지 기억하기 위해int visit[200];
선언
읽어온 원소로부터 queue에 push할 수 있는 원소를 push 하기
computers[q.front()][i = 0..n]
을 탐색해서,- q.front()와 연결되어 있고, (
computers[i][temp] == 1
) - 아직 방문하지 않았다면, (
visit[i] == 0
)
q.push();
- q.front()와 연결되어 있고, (
q.front() 원소가 답이 될 수 있는지, 혹은 정보 update가 가능한지 check 이후 행동
- 정보 update가 가능한 시점
- 더이상 탐색할 수 있는 원소가 없는 경우 한 네트워크를 다 찾은 것이므로, (
if(q.empty())
) - 다른 네트워크를 찾아야 한다.
for(int i = 0; i < n; i++){ if(visit[i] == 0){ q.push(i); visit[i] = ++answer; break; } }
- 위 과정을 거쳐도 추가된 원소가 없다면 (즉, 모든 컴퓨터를 탐색했다면) ,
return answer
- 더이상 탐색할 수 있는 원소가 없는 경우 한 네트워크를 다 찾은 것이므로, (
코드
#include <bits/stdc++.h>
using namespace std;
queue<int> q;
int visit[200], answer = 1;
int solution(int n, vector<vector<int>> computers) {
q.push(0);
visit[0] = answer;
while(-1){
if(q.empty()){
for(int i = 0; i < n; i++){
if(visit[i] == 0){
q.push(i);
visit[i] = ++answer;
break;
}
}
if(q.empty()) return answer;
}
int temp = q.front();
q.pop();
for(int i = 0; i < n; i++){
if(i == temp) continue;
else if(computers[i][temp] == 1 && visit[i] == 0){
q.push(i);
visit[i] = answer;
}
}
}
}
채점 결과
'Coding Test > programmers' 카테고리의 다른 글
프로그래머스 43164 - 여행경로 (c++) (0) | 2020.07.29 |
---|---|
프로그래머스 43163 - 단어 변환 (c++) (0) | 2020.07.29 |
프로그래머스 43165 - 타겟 넘버 (c++) (0) | 2020.07.29 |
프로그래머스 42747 - H-Index (c++) (0) | 2020.07.29 |
프로그래머스 42746 - 가장 큰 수 (c++) (0) | 2020.07.29 |