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

 

[ 문제 요약 ]

  • N * M 모양 게시판이 주어지고, 구멍은 *, 아니면 . 으로 모양이 주어집니다. 구멍을 폭이 1인 테이프를 이용해 막으려 합니다. 테이프를 끊어내는 횟수가 최소가 되도록 횟수를 출력합니다.
  • 테이프는 무한합니다.
  • 조건은, 구멍이 아닌 곳에 테이프를 붙이면 안 되며, 테이프를 붙인 곳에 여러 번 붙이는 것은 됩니다. 테이프는 가로로 길게, 세로로 길게만 붙일 수 있습니다.

 

[ 테스트 케이스 설명 ]

4 4// N,M 1<=50
*.*.// N개의 줄에 M개의 문자로 게시판이 추어짐, 구멍은 *, 아니면 .으로 주어짐
.***
***.
..*.
테이프를 끊어내는 최솟값 출력 : 4

 

 

[ 알고리즘 분류 ]

  • 이분 매칭

 

[ 문제 해설 ]

 

돌멩이 제거 문제와 같은 문제지만, 이 문제는 중간에 끊기는 부분이 있어 끊길 때마다 그 부분에 새로운 행/ 열을 추가한다 생각하고 연결 리스트를 만들어줘야 합니다. 이 문제를 풀기 전에 아래 문제를 풀면 도움이 됩니다.

 

https://kyjdummy.tistory.com/84

 

BOJ 백준 1867 돌멩이 제거

문제 : https://www.acmicpc.net/problem/1867 [ 문제 요약 ]N 행 N 열 격자로 나뉜 운동장 위에 K 개의 돌이 격자 하나에 하나씩 들어가 있습니다.한행이나 한열을 직선으로 가며 그곳의 돌을 모두 줍는 방식

kyjdummy.tistory.com

 

연결 리스트를 만들면 이 문제는 돌멩이 제거 문제와 같이 이분 그래프로 관계도를 만들 수 있게 되고, 이분 그래프의 간선은 구멍으로 볼 수 있게 되어 결과적으로 모든 간선에 대해 양쪽 노드 중 하나만 최소로 선택하는 최소 정점 커버 문제가 됩니다. 최소 정점 커버 문제는 쾨니그의 정리에 의해 최대 매칭과 동일함이 증명되어 있으므로 이분 매칭 문제로 풀면 됩니다.

 

여기서 문제는 구멍이 끊기는 구간에 새로운 행/열을 추가하는 걸 구현하는 일입니다.

 

구멍이 연속되지 않다는 것을 정확히 알기 위해 여러 가지 변수가 필요합니다.

 

먼저 행 또는 열의 값을 의미할 rowCnt, colCnt 변수가 필요하고,

 

이전 열 번호, 이전 행번호를 2차원에 담고 있을 colIdx, rowIdx 배열이 필요하고,

 

현재 상태(구멍인지 아닌지)를 담을 char 배열이 필요합니다.

 

탐색 순서는 왼쪽 위에서 오른쪽 아래로 내려가면서 탐색합니다.

 

탐색 시 현재보다 위쪽이 구멍이 아니면 행번호를 추가하고, 현재 보다 왼쪽이 구멍이 아니면 열 번호를 추가합니다.

 

그리고 그 값 그대로 리스트에 추가합니다. 그 후 일반 이분 매칭 문제처럼 풉니다.

 

[ 정답 코드 ]

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 MAX = 2500;
	static int Y, X;
	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());
		X = Integer.parseInt(st.nextToken());
		match = new int[MAX + 1];
		visitTime = new int[MAX + 1];
		adList = new ArrayList[MAX + 1];
		
		for(int i=0; i<adList.length; i++)
			adList[i] = new ArrayList<>();
		
		// 구멍이 연속되지 않으면 새로운 간선을 생성한다.
		// 그럼 행, 열을 의미할 값을 for문 안의 증가 변수를 사용하는게 아니라
		// 별도의 행 열 값을 의미할 변수를 생성해놓고 증가 변수와 분리해서 써야한다.
		int rowCnt = 0;
		int colCnt = 0;
		int rowIdx[][] = new int[Y + 1][X + 1];
		int colIdx[][] = new int[Y + 1][X + 1];
		char map[][] = new char[Y + 1][X + 1];
		for(int y=1; y<=Y; y++)
		{
			String str = br.readLine();
			for(int x=1; x<=X; x++)
			{
				map[y][x] = str.charAt(x-1);// 현재 위치의 상태 입력
				// 구멍일 경우 연산진행
				if(map[y][x] == '*')
				{
					// 위 쪽이 구멍이 아닌 경우, 새로운 행 번호 시작
					if(map[y-1][x] != '*')
						rowIdx[y][x] = ++rowCnt;
					else// 위 쪽이 구멍인 경우, 이전 위치에 있던 행번호를 그대로 복사해옴
						rowIdx[y][x] = rowIdx[y-1][x];
					// 왼쪽이 구멍이 아닌 경우 새로운 열 번호 시작
					if(map[y][x-1] != '*')
						colIdx[y][x] = ++colCnt;
					else// 왼쪽이 구멍인 경우 그 구멍의 열 번호를 그대로 복사해서 가져옴
						colIdx[y][x] = colIdx[y][x-1];
					// 행이 열을 갖도록 리스트 연결
					adList[rowIdx[y][x]].add(colIdx[y][x]);
				}
			}
		}
		
		int cnt = 0;
		
		for(int y=1; y<=rowCnt; y++)
		{
			++time;
			if(dfs(y))
				++cnt;
		}
		System.out.print(cnt);
	}
	
	static boolean dfs(int y)
	{
		for(int x : adList[y])
		{
			if(visitTime[x] == time)
				continue;
			
			visitTime[x] = time;
			
			if(match[x] == 0 || dfs(match[x]))
			{
				match[x] = y;
				return true;
			}
		}
		
		return false;
	}
}

'알고리즘 > 이분 매칭' 카테고리의 다른 글

BOJ 백준 1574 룩 어택  (0) 2025.05.28
BOJ 백준 9525 룩 배치하기  (0) 2025.05.28
BOJ 백준 1867 돌멩이 제거  (0) 2025.05.22
BOJ 백준 11378 열혈강호 4  (0) 2025.05.21
BOJ 백준 1671 상어의 저녁식사  (0) 2025.05.20

+ Recent posts