글 읽기 - 학교 가지마 최소 컷좀 도와주세요 ㅠ

kkw564 6년 전 0

민컷 개념, 정점을 2개로 쪼개는 개념을 처음 접해봐서 네트워크 플로우 단원이 조금 어렵네요

현재 정점을 두개로 쪼개서 정점 내부는 단방향 그래프로 만들었고 정점 내부의 용량은 1로 뒀습니다.

그 외에는 INF로 용량을 줘서 벽이 아닌이상 어디든지 갈 수 있도록 했는데요

4 5
.....
.K#..
...H.

.....

에는 3이 나오고

4 5
.....
.K...
...H.
.....

에는 4가 나오고

4 5
K....
...##
##...
....H

에는 1이 잘 나옵니다.

어느 부분을 더 고쳐야 할까요?

#include <iostream>
#include <cstdio>
#include <vector>
#include <memory.h>
#include <queue>
#include <cmath>
#include <map>

#define MAX_N 20002
#define INF 987654321
using namespace std;

char arr[101][101];
vector<int> adj[MAX_N];
map<pair<int, int>, int> cMap;
map<pair<int, int>, int> fMap;

int main()
{
	int n, m;
	int S = -1, T = -1, cnt = 0;
	int sx, sy, tx, ty;
	scanf("%d %d", &n, &m);

	getchar();
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			scanf("%c", &arr[i][j]);

			if (arr[i][j] == 'K')
			{
				S = cnt + 1;
				sx = j;
				sy = i;
			}
			else if (arr[i][j] == 'H')
			{
				T = cnt;
				tx = j;
				ty = i;
			}
			cnt += 2;
		}
		getchar();
	}


	if ((n == 1 && m == 1) || S == -1 || T == -1 || abs(sx - tx + sy - ty) == 1)
	{
		printf("-1\n");
		return 0;
	}

	// 정점을 2개로 쪼갠다.
	for (int i = 0; i < n * m; i++)
	{
		// in :: 0, 2, 4 ... out :: 1, 3, 5 ...
		cMap[{2 * i, 2 * i + 1}] = 1;
		adj[2 * i].push_back(2 * i + 1);
	}

	int from = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			if (j + 1 < m && arr[i][j] != '#' && arr[i][j + 1] != '#')
			{
				int to = from + 2;

				cMap[{from + 1, to}] = INF;
				cMap[{to + 1, from}] = INF;

				adj[from + 1].push_back(to);
				adj[to + 1].push_back(from);
			}

			if (i + 1 < n && arr[i][j] != '#' && arr[i + 1][j] != '#')
			{
				int to = 2 * m + from;

				cMap[{from + 1, to}] = INF;
				cMap[{to + 1, from}] = INF;

				adj[from + 1].push_back(to);
				adj[to + 1].push_back(from);
			}

			from += 2;
		}

	int totalFlow = 0;
	// 증가 경로를 못 찾을 때까지
	while (1)
	{
		int prev[MAX_N];
		memset(prev, -1, sizeof(prev));

		queue<int> q;
		// 싱크를 처음 push 해준다.
		q.push(S);

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

			//cout << "cur :: " << cur << endl;

			for (int i = 0; i < adj[cur].size(); i++)
			{
				int next = adj[cur][i];

				if (prev[next] != -1)
					continue;

				if (cMap[{cur, next}] - fMap[{cur, next}] > 0)
				{
					q.push(next);

					prev[next] = cur;

					if (next == T)
						break;
				}
			}
		}

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

		for (int i = T; i != S; i = prev[i])
		{
			fMap[{prev[i], i}] += 1;
			fMap[{i, prev[i]}] -= 1;
			//	cout << "i :: " << i << " " << "prev[i] :: " << prev[i];
			//	cout << " f[prev[i]][i] :: " << f[prev[i]][i] << endl;
		}

		totalFlow += 1;
		//cout << ":::: flow ::::: " << flow << endl;
	}


	printf("%d\n", totalFlow);


	return 0;
}

kks227 6년 전 0

3, 4가 맞지 않나요?

kkw564 6년 전 0

3,4가 무슨말씀이신가요??

kks227 6년 전 0

말씀하신 저 두 예제의 답이 이상하게 나온다고 말씀하신 것으로 해석했는데, 저 답들이 정답이 아닌가 합니다.

kkw564 6년 전 0

아뇨 ㅎ 제가 말씀드린건.. 저렇게 잘나오는데 왜 안돼냐 생각이들어서 질문했었어요

그런데 어디 가는길에 생각을해봤는데 제가 오른쪽과 아래부분가는길에 대해서만 생각을해줘서

위와 왼쪽으로 가는길에 대해서 추가해주면 ac를 받을 수 있지 않을까생각이드네요

맞을까요..??

kks227 6년 전 0

사방에 대해 다 추가를 해야 할 듯 합니다.

kkw564 6년 전 1

감사합니다 ㅎ

항상 블로그 잘 보고있습니다. 덕분에 많이배우고있습니다.

kks227 6년 전 0

누추한 블로그를 찾아주셔서 감사합니다. 요즘 귀차니즘에 시달려서 다음 글이 또 몇 달째 올라오지 않고 있는데...

kkw564 6년 전 1

덕분에 플로우까지올수있었네요

저희 스터디도 라이 블로그 기준으로 문제도 풀구요 ㅋㅋ

혹시 모르는게 또있다면 여기서여쭤볼게요 ㅠㅠ

kks227 6년 전 1

헐 그런가요... 스터디에 제 블로그가 쓰이고 있다니, 그런 일이 있을줄까진 몰랐군요.

사람들에게 도움이 된다니 다행입니다. 저도 배우는 처지인지라 몇몇 글은 필력이 부족할 수도 있을 텐데...

언제든지 질문하셔도 좋습니다. 저도 간혹 허를 찔리는 질문이 들어오는데, 그땐 많은 공부가 됩니다.

kkw564 6년 전 0

라이님 이 코드가 왜 틀린지 좀 봐주실 수 있나요..?

pq를 쓴이유는 위의 코드에서

4 5
.....
....H
K....
.....

를 2로 인식하더라구요 답은 3인데, 그래서 pq로 가장 왼쪽 위 노드부터 방문할 수 있다면 먼저 방문하도록 설정하여 저런 현상까지 모두 해결하였는데

틀렸습니다가 계속 뜨는걸 보니 다른 예외라던지 실수가 있는것같아요 제 코드에요

확인하시면 한번만 봐주시면 감사하겠습니다!

#include <iostream>
#include <cstdio>
#include <vector>
#include <memory.h>
#include <queue>
#include <cmath>
#include <map>
#include <functional>

#define MAX_N 20002
#define INF 987654321
using namespace std;

char arr[101][101];
vector<int> adj[MAX_N];
map<pair<int, int>, int> cMap;
map<pair<int, int>, int> fMap;

int main()
{
	int n, m;
	int S = -1, T = -1, cnt = 0;
	int sx, sy, tx, ty;
	scanf("%d %d", &n, &m);

	getchar();
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			scanf("%c", &arr[i][j]);

			if (arr[i][j] == 'K')
			{
				S = cnt + 1;
				sx = j;
				sy = i;
			}
			else if (arr[i][j] == 'H')
			{
				T = cnt;
				tx = j;
				ty = i;
			}
			cnt += 2;
		}
		getchar();
	}


	if ((n == 1 && m == 1) || S == -1 || T == -1 || abs(sx - tx + sy - ty) == 1)
	{
		printf("-1\n");
		return 0;
	}

	// 정점을 2개로 쪼갠다.
	for (int i = 0; i < n * m; i++)
	{
		// in :: 0, 2, 4 ... out :: 1, 3, 5 ...
		cMap[{2 * i, 2 * i + 1}] = 1;
		adj[2 * i].push_back(2 * i + 1);
	}

    // 간선 연결 작업(왼쪽 위부터 오른쪽 아래로 작업)
	int from = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			if (j + 1 < m && arr[i][j] != '#' && arr[i][j + 1] != '#')
			{
				int to = from + 2;

				cMap[{from + 1, to}] = INF;
				cMap[{to + 1, from}] = INF;

				adj[from + 1].push_back(to);
				adj[to + 1].push_back(from);
			}

            // 간선 중복 연결인 것 같아 역방향쪽인것은 주석처리 했습니다.
            /*
			if (j - 1 >= 0&& arr[i][j] != '#' && arr[i][j - 1] != '#')
			{
				int to = from - 2;

				cMap[{from + 1, to}] = INF;
				cMap[{to + 1, from}] = INF;

				adj[from + 1].push_back(to);
				adj[to + 1].push_back(from);
			}
            */
			if (i + 1 < n && arr[i][j] != '#' && arr[i + 1][j] != '#')
			{
				int to = 2 * m + from;

				cMap[{from + 1, to}] = INF;
				cMap[{to + 1, from}] = INF;

				adj[from + 1].push_back(to);
				adj[to + 1].push_back(from);
			}

            /*
			if (i - 1 >= 0 && arr[i][j] != '#' && arr[i - 1][j] != '#')
			{
				int to = from - 2 * m;

				cMap[{from + 1, to}] = INF;
				cMap[{to + 1, from}] = INF;

				adj[from + 1].push_back(to);
				adj[to + 1].push_back(from);
			}
            */
			from += 2;
		}

	int totalFlow = 0;
	// 증가 경로를 못 찾을 때까지
	while (1)
	{
		int prev[MAX_N];
		memset(prev, -1, sizeof(prev));

		priority_queue<int,vector<int>, greater<int>> pq;
		// 싱크를 처음 push 해준다.
		pq.push(S);

		while (!pq.empty())
		{
			int cur = pq.top();
			pq.pop();

			for (int i = 0; i < adj[cur].size(); i++)
			{
				int next = adj[cur][i];

				if (prev[next] != -1)
					continue;

				if (cMap[{cur, next}] - fMap[{cur, next}] > 0)
				{
					pq.push(next);

					prev[next] = cur;

					if (next == T)
						break;
				}
			}
		}

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

		for (int i = T; i != S; i = prev[i])
		{
			fMap[{prev[i], i}] += 1;
			fMap[{i, prev[i]}] -= 1;
		}

		totalFlow += 1;
	}


	printf("%d\n", totalFlow);


	return 0;
}

kkw564 6년 전 0

아.. pq로 하니

4 5
.....
.....
.K.H.

.....

이게 3이 나오네요 ㅠ 도대체 어떻게 해야되는거죠.. 포드 풀커슨으로 안되는게 아닐텐데

kks227 6년 전 2

일단 읽고는 있는데, 위에선 드러나지 않은 문제점이지만 예외 처리에서

abs(sx - tx + sy - ty) == 1

이게 진짜 -1이 맞나요? 시작점이 (2, 4)고 도착점이 (4, 1)이면 저게 true지만 답은 -1이 아니어야 합니다.

abs(sx-tx) + abs(sy-ty) == 1 로 고치는 게 맞아 보입니다.

kks227 6년 전 0

그리고 주석 처리된 부분을 풀어야 할 듯 싶습니다. 4방향으로 모두 간선을 다셔야 할 거에요.

또 결정적인 것이 57~62번 줄에서 분명 정점을 2개로 쪼개놓고 있고, 입력을 받을 때도 그걸 처리하고 있는데

정작 인접한 칸끼리 간선을 연결할 때는 쪼갠 정점의 구분이 없네요.

정점 v를 들어오는 정점 v1과 나가는 정점 v2로 쪼갰을 때, u에서 v로 갈 수 있다면 u2 -> v1로 간선을 연결해야 할 텐데

코드상의 +2라던가 +2*m 등은 저 번호와 아무 상관이 없고, 결과적으로 from과 to 모두 들어오는 정점의 번호가 되겠군요. 이 부분을 고치셔야 할 듯 합니다. 나가는 정점 -> 들어오는 정점으로...

그리고 플로우에서는 역방향간선도 인접 리스트에 넣어줘야 합니다. 예를 들면 60~61번 줄의 경우 이뿐 아니라

cMap[{2 * i + 1, 2 * i}] = 0;

adj[2 * i + 1].push_back(2 * i);

이렇게 플로우 그래프상에서 반대방향 간선도 추가로 필요합니다. 처음엔 capacity가 0이지만, 순방향으로 흐를 때 유량을 상쇄시키면서 역방향으로 이동하는 경로를 찾으려면 저 역방향 간선이 필요하죠.

kkw564 6년 전 0

이렇게 생각했는데 일단 쪼갠 정점 사이의 역방향 간선은 다시 추가했습니다.

지금 제가 생각하는 방식은, char형 그림 따로(# , k, h , .으로 이루어 진 배열), 그리고 쪼개어진 정점 넘버링을 map STL로 관리중이고 간선을 adj로 관리중이구여

아래 코드 부분이

from이 0부터 시작하며 쪼개어진 정점의 왼쪽것을 계속 가리키고 있도록 했습니다. 0, 2, 4 , 6, ...

저는 맞다고 생각하고 그래프를 생성하였는데 정확히 어떻게 틀렸다는건가요..? ㅠㅠ

이게 사람이 맞다고 생각하고있으니 잘안보이네요 ㅠㅠ

그리고 제가 그 주석처리 한부분은

어짜피 왼쪽위에서 오른쪽아래로가며 서로 반대편것도 계속 추가해주고있기때문에 오른쪽아래에서 왼쪽위 부분은 필요없지않나요..??

라이님 너무 오래 물어서 죄송해여ㅠㅠ

	// 간선 연결 작업(왼쪽 위부터 오른쪽 아래로 작업)
	int from = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			if (j + 1 < m && arr[i][j] != '#' && arr[i][j + 1] != '#')
			{
				int to = from + 2;

				cMap[{from + 1, to}] = INF;
				cMap[{to + 1, from}] = INF;

				adj[from + 1].push_back(to);
				adj[to + 1].push_back(from);
			}

			if (i + 1 < n && arr[i][j] != '#' && arr[i + 1][j] != '#')
			{
				int to = 2 * m + from;

				cMap[{from + 1, to}] = INF;
				cMap[{to + 1, from}] = INF;

				adj[from + 1].push_back(to);
				adj[to + 1].push_back(from);
			}

			from += 2;
		}

kkw564 6년 전 0

문제 해결했습니다!

역방향 간선 및 CAPACITY를 추가해주니 되네요

그런데 갑자기 좀 궁금해진게 왜 역방향 간선을 넣어야 하는건가요..?

라이님 블로그 말씀대로 보통문제에서 역방향을 안해도 맞는 문제가 있다고했는데

이 문제는 왜 역방향 간선 및 capacity를 추가해야하나요?

#include <iostream>
#include <cstdio>
#include <vector>
#include <memory.h>
#include <queue>
#include <cmath>
#include <map>
#include <functional>

#define MAX_N 20002
#define INF 987654321
using namespace std;

char arr[101][101];
vector<int> adj[MAX_N];
map<pair<int, int>, int> cMap;
map<pair<int, int>, int> fMap;

int main()
{
	int n, m;
	int S = -1, T = -1, cnt = 0;
	int sx, sy, tx, ty;
	scanf("%d %d", &n, &m);

	getchar();
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			scanf("%c", &arr[i][j]);

			if (arr[i][j] == 'K')
			{
				S = cnt + 1;
				sx = j;
				sy = i;
			}
			else if (arr[i][j] == 'H')
			{
				T = cnt;
				tx = j;
				ty = i;
			}
			cnt += 2;
		}
		getchar();
	}


	if ((n == 1 && m == 1) || S == -1 || T == -1 || abs(sx - tx) + abs(sy - ty) == 1)
	{
		printf("-1\n");
		return 0;
	}

	// 정점을 2개로 쪼갠다.
	for (int i = 0; i < n * m; i++)
	{
		// in :: 0, 2, 4 ... out :: 1, 3, 5 ...
		cMap[{2 * i, 2 * i + 1}] = 1;
		adj[2 * i].push_back(2 * i + 1); 
		
		cMap[{2 * i + 1, 2 * i}] = 0;
		adj[2 * i + 1].push_back(2 * i);
	}

	// 간선 연결 작업(왼쪽 위부터 오른쪽 아래로 작업)
	int from = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			if (j + 1 < m && arr[i][j] != '#' && arr[i][j + 1] != '#')
			{
				int to = from + 2;

				cMap[{from + 1, to}] = INF;
				cMap[{to, from + 1}] = 0;

				cMap[{to + 1, from}] = INF;
				cMap[{from, to + 1}] = 0;

				adj[from + 1].push_back(to);
				adj[to].push_back(from + 1);

				adj[to + 1].push_back(from);
				adj[from].push_back(to + 1);
			}

			if (i + 1 < n && arr[i][j] != '#' && arr[i + 1][j] != '#')
			{
				int to = 2 * m + from;

				cMap[{from + 1, to}] = INF;
				cMap[{to, from + 1}] = 0;

				cMap[{to + 1, from}] = INF;
				cMap[{from, to + 1}] = 0;

				adj[from + 1].push_back(to);
				adj[to].push_back(from + 1);

				adj[to + 1].push_back(from);
				adj[from].push_back(to + 1);
			}

			from += 2;
		}

	int totalFlow = 0;

	// 증가 경로를 못 찾을 때까지
	while (1)
	{
		int prev[MAX_N];
		memset(prev, -1, sizeof(prev));

		queue<int> q;

		q.push(S);

		while (!q.empty())
		{
			int cur = q.front();

			q.pop();

			for (int i = 0; i < adj[cur].size(); i++)
			{
				int next = adj[cur][i];

				if (prev[next] != -1)
					continue;

				if (cMap[{cur, next}] - fMap[{cur, next}] > 0)
				{
					q.push(next);

					prev[next] = cur;

					if (next == T)
						break;
				}
			}
		}

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

		for (int i = T; i != S; i = prev[i])
		{
			fMap[{prev[i], i}] += 1;
			fMap[{i, prev[i]}] -= 1;
		}

		totalFlow += 1;
	}


	printf("%d\n", totalFlow);


	return 0;
}

kks227 6년 전 0

어... 지금 역방향 간선이라는 개념이 이 스레드(?)에서 2개가 등장해서 개념을 헷갈려하시는 것 같군요.

제가 말한 모든 플로우 그래프에 있어야 하는 역방향 간선은 플로우 그래프에서 u->v로 용량 c인 간선이 있을 경우 v->u로도 용량 0인 간선이 있어야한다는 걸 말합니다.

이 문제에서는 추가로, 오른쪽 방향이나 아래쪽 방향으로 가는 간선 말고도 '그 역방향'인, 왼쪽 방향이나 위쪽 방향으로 가는 간선도 필요했던 겁니다.

kkw564 6년 전 0

@kks227님, 문제 푼게 있는데 궁금해서 그런데 도와주실 수 있나요 ㅠㅠ?

kks227 6년 전 0

왜그러시나요?

kkw564 6년 전 0

https://www.acmicpc.net/board/... 이 링크에 대해 답변좀 해주실 수 있나요..?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

학교 가지마 최소 컷좀 도와주세요 ㅠ

kkw564 6년 전 0

kks227 6년 전 0

kkw564 6년 전 0

kks227 6년 전 0

kkw564 6년 전 0

kks227 6년 전 0

kkw564 6년 전 1

kks227 6년 전 0

kkw564 6년 전 1

kks227 6년 전 1

kkw564 6년 전 0

kkw564 6년 전 0

kks227 6년 전 2

kks227 6년 전 0

kkw564 6년 전 0

kkw564 6년 전 0

kks227 6년 전 0

kkw564 6년 전 0

kks227 6년 전 0

kkw564 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말