[백준] No.2570 - 비숍2 (C++, 이분 매칭)

문제

 

https://www.acmicpc.net/problem/2570

2570번: 비숍2

 

풀이

 

solved.ac 난이도: Platium 2

 

이분할 집합에 대해 곰곰이 생각해봐야 풀 수 있는 이분 매칭 문제.

 

한 좌표에 비숍을 놓으면 해당 비숍에 의해 더 이상 다른 말을 놓을 수 없는 두 대각선이 생긴다.

하지만 좌표와 두 대각선을 이분 매칭을 진행하는 것은 불가능하다.

(하나의 좌표에 대각선을 두 개 매칭해 주어야하기 때문에)

 

따라서 방향이 다른 대각선끼리 집합을 만들어 이분 매칭을 진행해야 한다.

한 대각선('/'방향)과 다른 방향의 한 대각선 ('\'방향)을 매칭 한다면 결과적으로 두 대각선이 교차하는 유일한 좌표를 구할 수 있다.

이는 결과적으로, 해당 교차 좌표에 비숍을 놓는 것과 동일한 역할을 한다.

 

 

이러한 이분 그래프를 구현하기 위해 '/' 방향 대각선을 dir1,  '\' 방향 대각선을 dir2로 구분하자.

 

dir1과 dir2를 이어 주기 위해서 각 칸을 방문하면서 해당 좌표는 몇 번째 대각선에 포함되는지 dir_idx[방향][r][c]에 저장하는 DFS를 구현하였다.

 

void DirCheckDFS(int r, int c, int idx ,int order){
  visited[r][c] = true;
  //r,c는 order번째 대각선임
  dir_idx[idx][r][c] = order;
 
  int next_r, next_c;
  for(int i=0; i<2 ; ++i){
    next_r = r + change_pos[i][0];
    next_c = c + change_pos[i][1];
 
    //범위 확인
    if(next_r <0 || board_size <= next_r || next_c < 0 || board_size <= next_c )
      continue;
    
    if(visited[next_r][next_c] || is_obstacle[next_r][next_c])
      continue;
    
    DirCheckDFS(next_r, next_c, idx, order);
  }
}

 

이제 모든 칸들이 포함되어 있는 대각선을 구했으므로 '/'방향 대각선의 정점들에서 '\' 대각선으로 간선 연결해주고 이분 매칭을 진행하면 된다.

 

 

 

참고로 종만북에도 등장하는 문제이다.

[AlgoSpot] 비숍(BISHOPS)

 

코드