BOJ 백준 16726 영과일 학회방

문제 : https://www.acmicpc.net/problem/16726

 

[ 문제 요약 ]

• 직사각형 바닥이 주어질 때, 21 타일과 11타일을 최소한을 놓을 때, 몇 개의 타일을 놓을 수 있는지 구하는 문제입니다. 단, 기둥이 있는 바닥에는 타일을 놓을 수 없습니다.

 

[ 테스트 케이스 설명 ]

3 4// 행, 열(1<=50)
.X..// X는 기둥, .은 바닥
...X
...X
답 : 5

 

 

[ 알고리즘 분류 ]

• 그래프 이론
• 최대 유량
• 이분 매칭
• 격자 그래프

 

[ 문제 해설 ]

2 *1 과 1 * 1을 사용해 타일을 최소로 놓으려면, 2 * 1을 최대로 사용해야 합니다.

 

2 * 1을 최대로 사용하는 것은 이분 매칭으로 구할 수 있습니다. 각 타일을 체스판처럼 구분하고, 체스판의 흰색, 또는 검은색 기준으로 왼쪽, 오른쪽 노드로 구분해 인접 리스트를 만들어 최대 매칭을 구하면 됩니다.

 

답을 구할 때는, 총 빈칸의 합에서, 2 * 1 타일의 수를 빼면 됩니다. 그 이유는 타일의 빈칸의 총합이 A라고 할 때, 2 * 1타일의 개수가 B 이면, A - B2 = 1* 1 타일의 개수가 됩니다. 그럼 모든 타일의 개수는 (A - B*2 + B)가 되어 A-B가 타일의 개수가 됩니다.

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

class Main{
	
	static final int dxy[][] = {{1,0},{0,1},{-1,0},{0,-1}};
	
	static int totalBlank;
	static int Y, X;
	static int idx[][];
	static boolean isPos[][];

	// 이분 매칭시 사용
	static int time;
	static int match[];
	static int visitTime[];
	static List<Integer> adList[];
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		Y = Integer.parseInt(st.nextToken());// 행(1<=50)
		X = Integer.parseInt(st.nextToken());// 열(1<=50)
		idx = new int[Y + 2][X + 2];
		isPos = new boolean[Y + 2][X + 2];

		boolean flag;
		int i = 0;
		int j = 0;
		for(int y=1; y<=Y; y++)
		{
			flag = y % 2 == 1;// 타일을 체스판 처럼 구분하기 위한 값
			String str = br.readLine();
			for(int x=1; x<=X; x++,flag = !flag)
			{
				isPos[y][x] = str.charAt(x - 1) == '.';
				
				if(!isPos[y][x])
					continue;
				
				++totalBlank;
				
				idx[y][x] = flag ? ++i : ++j;
			}
		}
		
		match = new int[j + 1];
		visitTime = new int[j + 1];
		adList = new ArrayList[i + 1];
		
		for(int s=0; s<=i; s++)
			adList[s] = new ArrayList<>();
		
		for(int y=1; y<=Y; y++)
		{
			int x = y % 2 == 1 ? 1 : 2;// 타일 구분을 위해 사용
			for(; x<=X; x+=2)
			{
				if(!isPos[y][x])
					continue;
				
				for(int xy[] : dxy)
				{
					int nextY = y + xy[0];
					int nextX = x + xy[1];
					if(isPos[nextY][nextX])
						adList[idx[y][x]].add(idx[nextY][nextX]);
				}
			}
		}
		
		int cnt = 0;
		
		for(int L=1; L<=i; L++)
		{
			++time;
			if(dfs(L))
				++cnt;
		}
		// 빈칸 총합에서 두칸 짜리 타일 값을 빼면 최종 타일의 개수가 나옴
		System.out.print(totalBlank - cnt);
	}
	static boolean dfs(int L)
	{
		for(int R : adList[L])
		{
			if(visitTime[R] == time)
				continue;
			
			visitTime[R] = time;
			
			if(match[R] == 0 || dfs(match[R]))
			{
				match[R] = L;
				return true;
			}
		}
		return false;
	}
}