[백준] 1325 효율적인 해킹 c++ 구현

목차

 

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

1325번: 효율적인 해킹

문제

 

문제 구현 방향

나는 인접리스트를 활용한 dfs로 접근해 보았다.

그 과정에서 오름차순 정렬은 sort함수를 통해, 최댓값은 max함수를 통해 해결하고자 했다.

 

 

문제 풀이 시 주의점

시작점을 여러 곳에서 해보아야 하므로 방문배열을 초기화 해주어야 한다.

해킹이 가장 많은 컴퓨터가 여러개이므로 따로 저장해서 정렬해 주는 것이 살짝 까다로웠다.

 

 

문제 풀이

기존 dfs탐색 방법으로 하되 시작점 모든 곳에서 하여 노드 개수를 세어 저장해 주면 된다.

해킹 개수를 인접리스트로 만들어 해킹 개수가 같은 컴퓨터들끼리 저장해 놓는 것이 포인트였다.

 

 

 

 

코드 구현

#include <vector>
#include <iostream>
#include <stack>  
#include <cmath>   //max사용을 위한 헤더
#include<algorithm>  //sort사용을 위한 헤더
using namespace std;

vector<bool> visit(100000, false);    //방문한 곳을 표시하기 위한 배열
vector<int> computer[100000];     //컴퓨터의 관계를 나타낸 배열
vector<int> countComputer[100000];     //카운트해서 저장할 배열
vector<int>Compare;   //가장 큰 출발점만 저장해 오름차순 정렬할 배열

void dfs(int start, int *cnt) {
	visit[start] = true;  //방문한 곳 푯표시
	(*cnt)++;
	for (int i = 0; i < computer[start].size(); i++) {   
		int next = computer[start][i];
		if (!visit[next]) {     // 방문하지 않았다면 다시 dfs 호출
			dfs(next, cnt);
		}
	}
	
}

int main() {
	int N, M, i, A, B, cnt =0, maxcount =0;
	int* pcnt=&cnt;
	cin >> N >> M;

	for (i = 0; i < M; i++) {
		cin >> A >> B;
		computer[B].push_back(A);
	}

	for (i = 1; i <= N; i++) {
		*pcnt = 0;
		dfs(i, pcnt);         
		maxcount = max(maxcount, *pcnt);
		countComputer[*pcnt].push_back(i);     //카운트안에 출발점들 저장

		fill(visit.begin(), visit.end(), false);     //다시 방문한 곳 초기화
	}
	for (i = 0; i < countComputer[maxcount].size(); i++) {  //가장 큰 count를 가진 출발점만 따로 저장 (sort를 하기 위함)
		Compare.push_back(countComputer[maxcount][i]);
	}

	sort(Compare.begin(), Compare.end());  //오름 차순 정렬

	for (auto iter : Compare) {
		cout << iter << '\n';
	}


}

 

dfs에 대해서 잘 이해하고 있다면 그렇게 어려운 문제는 아니였다!