백준1325 - 효율적인 해킹

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

1325번: 효율적인 해킹

간단한 bfs 문제였다. 입력시에 b가 출발점이고 a가 도착점이라는 사실만 잊지 않으면 쉽게 푼다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 10001
using namespace std;

int N, M; //N개의 컴퓨터의 갯수, M개의 연결 정보 갯수
int a, b; //a는 도착지, b는 출발지
int cnt = 0; //최대로 탐색 가능한 컴퓨터의 수
bool visit[MAX]; //컴퓨터 방문여부


vector<int> v[MAX]; //컴퓨터 연결 정보
vector<int> ans; //답으로 쓸 공간
vector<int> temp; //bfs에서 탐색할 때 방문한 컴퓨터의 번호를 저장하는 공간

void bfs(int x) {
	queue<int> q;
	q.push(x);
	visit[x] = true;
	temp.push_back(x);

	while (!q.empty()) {
		x = q.front();
		q.pop();

		for (int i = 0; i < v[x].size(); i++) {
			if (!visit[v[x][i]]) {
				q.push(v[x][i]);
				visit[v[x][i]] = true;
				temp.push_back(v[x][i]);
			}
		}
	}
}

int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &a, &b);
		v[b].push_back(a); //b를 해킹하면 a를 해킹할 수 있다.(b에서 a로 갈 수 있다.)
	}

	for (int i = 1; i <= N; i++) {
		memset(visit, false, sizeof(visit)); //모든 컴퓨터를 미방문처리
		temp.clear(); //해킹할 수 있는 컴퓨터의 번호를 담는 공간 초기화
		bfs(i);
		if (cnt > temp.size()) { //현재 해킹할 수 있는 컴퓨터의 수가 이전의 최대보다 적으면
			continue; //무시
		}
		else if (cnt == temp.size()) { //현재 해킹할 수 있는 컴퓨터의 수가 이전의 최대와 같으면
			ans.push_back(i); //현재 컴퓨터를 답에 넣는다.
		}
		else { //현재 해킹할 수 있는 컴퓨터의 수가 이전의 최대보다 많으면
			cnt = temp.size(); //이전의 최대를 현재로 바꾸고
			ans.clear(); //답을 초기화 한 공간을 날린 뒤
			ans.push_back(i); //현재 컴퓨터를 답에 넣는다.
		}
	}

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

	//출력
	for (int i = 0; i < ans.size(); i++) {
		printf("%d ", ans[i]);
	}
}