BOJ - 17199번 Milk Factory (C++)

문제 출처: https://www.acmicpc.net/problem/17199

문제 난이도

Silver 1

문제 접근법

1번부터 N번까지 가는데 입력값으로 제시된 방향들이 단반향이라 한 역을 양방향화 시키면 끝까지 갈 수 있다. 근데 이 때 최소값인 수를 출력하는 문제다.

통과 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#define INF 987654321

using namespace std;

int arr[101][101];

int main() {
	int N;
	cin >> N;
	
	for (int i = 0; i < N - 1; i++) {
		int a, b;
		cin >> a >> b;
		arr[a][b] = 1;
	}
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (arr[i][k] == 1 && arr[k][j] == 1) arr[i][j] = 1;
			}
		}
	}
	int res = INF;
	for (int i = 1; i <= N; i++) {
		int cnt = 0;
		for (int j = 1; j <= N; j++) {
			if (arr[j][i] == 1) cnt++;
		}
		if (cnt == N - 1) {
			res = i;
			break;
		}
	}
	res = res == INF ? -1 : res;
	cout << res;

	return 0;
}

피드백

처음에 문제가 영어라 그런가 문제 해석하는데도 시간이 걸렸고.. 1번부터 N번까지 연결된 걸 찾으면 된다는 생각에 다익스트라와 비슷한 형태로 풀었지만 틀렸다! 단방향인걸 체크하지 못해서 그렇다 그 후 N값도 작고 시간 제한이 2초임을 감안해 플로이드와샬 방법을 생각했다.