[BOJ] #7616 _ 교실로 가는 길

[교실로 가는 길] https://www.acmicpc.net/problem/7616

7616번: 교실로 가는 길

네트워크 플로우를 이용할 수 있다.

단, 교차로에서 친구를 마주치면 안되기 때문에 정점의 중복 방문을 제외시켜야 한다.

 

해당 문제는 최대 정점의 갯수가 5000개로 아주 크다.

뿐만 아니라, 모든 경로를 마지막에 출력해주어야 하므로 경로를 저장할 변수도 필요하다.

처음에는 메모리 제한을 신경쓰지 않고 풀었다가 메모리 초과가 발생하였다.

메모리를 잘 생각해서 풀어야 한다.

 

교차로를 이용할 수 있는 사람의 수는 한명이기 때문에,

4byte인 int형 대신 1byte인 bool형을 이용하여 메모리의 크기를 줄일 수 있다.

 

[ 소스 코드 ]

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 5001
#define INF 999999999

using namespace std;

bool chk[MAX], c[MAX][MAX], f[MAX][MAX];
int N, K, visit[MAX];
vector<int> adj[MAX], path;

void init();
int maxFlow(int S, int T);
int main() {
	for (int i = 1;; i++) {
		scanf("%d %d", &K, &N);
		if (N == 0 && K == 0) break;

		for (int j = 1; j <= N; j++) {
			int input[MAX], idx = 0;
			char tmp;
			while (1) {
				scanf("%d%c", &input[idx++], &tmp);
				if (tmp == '\n') break;
			}
			
			for (int k = idx - 1; k >= 0; k--) {
				adj[j].push_back(input[k]);
				c[input[k]][j] = 1;
				c[j][input[k]] = 1;
			}
		}

		printf("Case %d:\n", i);
		if (maxFlow(1, 2) >= K) {
			for (int i = path.size() - 1; i >= 0; i--) {
				if (path[i] != 2) printf("%d ", path[i]);
				else printf("%d\n", path[i]);
			}
		}
		else printf("Impossible\n");
		printf("\n");

		init();
	}

	return 0;
}

void init() {
	path.clear();
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			c[i][j] = 0;
			f[i][j] = 0;
		}
		chk[i] = 0;
		adj[i].clear();
	}
}

int maxFlow(int S, int T) {
	int result = 0;

	while (result < K) {
		fill(&visit[0], &visit[MAX], -1);

		queue<int> q;
		q.push(S);
		while (!q.empty()) {
			int a = q.front();
			q.pop();
			for (int i = 0; i < adj[a].size(); i++) {
				int b = adj[a][i];

				if (chk[b] == 0 && visit[b] == -1 && c[a][b] - f[a][b] > 0) {
					q.push(b);
					visit[b] = a;
					if (b == T) break;
				}
			}
		}

		if (visit[T] == -1) break;

		for (int i = T; i != S; i = visit[i]) {
			chk[i] = 1;
			path.push_back(i);
			f[visit[i]][i] = 1;
			f[i][visit[i]] = 0;
		}
		chk[T] = 0;
		path.push_back(S);
		result++;
	}

	return result;
}