[editorial] APC - G. Bishops

  • Toivoa
    Toivoa

    Astein 님 혼자 푼 Bishops 문제를 낸 Toivoa 입니다.
    출제 후기부터 먼저 쓰면 원래는 Queen으로 냈다가 생각보다 어렵다는것을 깨닫고 급하게 Bishop으로 수정하느라 문제 statement를 미처 제대로 수정하지 못했습니다. 입/출력 형식을 설명하는 부분에서 Queen이 남아있던 것 때문에 말리신 분들도 여럿 계실거라 생각하고 미리 사과부터 드립니다.
    그리고 이후에 안 이야기지만 몇년 전에 KOI 중등부 문제로 똑같은 문제가 출제되었었다고 들었습니다. ㅠㅠ
    [문제 풀이]
    문제에 Backtracking이 나와있는 만큼 Backtracking으로 풀 수 있는 문제가 아닙니다. 참고로 judge의 입력을 backtracking을 이용해서 돌려봤을 때 1분 이상 걸렸습니다.
    이 문제는 maximum bipartite matching을 이용해서 풉니다.
    bipartite graph는 Bishop이 갈 수 있는 / 방향의 맵과 \ 방향의 맵을 만든 후 겹치는 부분에서 그래프의 양쪽을 연결해주는 식으로 만듭니다.
    예를 들어 4x4에서 다음과 같이 생긴 경우 (제대로 보이지 않는다면 메모장에 복사해서 보세요.)
    ....
    .*.*
    **.
    ..    *
    / 방향의 맵은 다음과 같이 만들어집니다.
    1234
    2*4*
    **7
    56    *
    또한 \ 방향의 맵은 다음과 같이 만들어집니다.
    1234
    5*2*
    **2
    67    *
    여기에서 / 방향과 \ 방향에서 서로 겹치는 부분을 이분 그래프(bipartite graph)로 이어준 후에 (예에서는 (1, 1) (2, 2) (3, 3) (4, 4) (2, 5), (4, 2), (7, 2), (5, 6), (6, 7) 이 되겠죠?) maximum bipartite matching을 돌려주면 됩니다.
     
    maximum bipartite matching은 max-flow를 이용해서 구할 수 있습니다. 여기에서는 max-flow와 maximum bipartite matching에 대한 설명은 생략합니다.
    [정답 소스코드]

    #include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int n;
char table[11][11];
int xtable[2][11][11];
int cap[1000][1000];
int flow[1000][1000];
vector<int> v[1000];
int s, e;
int from[1000];
bool go(int s, int e)
{
 queue<int> q;
 int c, d;
 q.push(s);
 fill(from, from + 1000, -1);
 
 while (!q.empty())
 {
  c = q.front(); q.pop();
  for (size_t i = 0; i < v[c].size(); ++i)
  {
   d = v[c][i];
   if (from[d] != -1) continue;
   if (cap[c][d] - flow[c][d] > 0)
   {
    q.push(d);
    from[d] = c;
    if (d == e) return true;
   }
  }
 }
 return false;
}
int pushFlow(int s, int e)
{
 int ret = 0;
 while (go(s, e))
 {
  ++ret;
  int y = e, x = from[e];
  while (x != -1)
  {
   --flow[y][x];
   ++flow[x][y];
   y = x; x = from[x];
  }
 }
 return ret;
}
int main()
{
 int t;
 scanf("%d", &t);
 while (t--)
 {
  scanf("%d", &n);
  fill(xtable[0][0], xtable[2][0], 0);
  fill(cap[0], cap[1000], 0);
  fill(flow[0], flow[1000], 0);
  for (int i = 0; i < n; ++i)
   scanf("%s", table[i]);
  int num = 0;
  s = 0;
  
  // / 방향
  for (int i = 0; i < n * 2; ++i)
  {
   int x, y;
   if (i < n)
   {
    x = 0; y = i;
   }
   else
   {
    x = i - n + 1; y = n - 1;
   }
   bool prev = false;
   while (x < n && y >= 0)
   {
    if (table[x][y] == '.')
    {
     if (!prev)
     {
      prev = true;
      ++num;
     }
     xtable[0][x][y] = num;
    }
    else
     prev = false;
    ++x; --y;
   }
  }
  // \ 방향
  for (int i = 0; i < n * 2; ++i)
  {
   int x, y;
   if (i < n)
   {
    x = 0; y = n - 1 - i;
   }
   else
   {
    x = i - n + 1; y = 0;
   }
   bool prev = false;
   while (x < n && y < n)
   {
    if (table[x][y] == '.')
    {
     if (!prev)
     {
      prev = true;
      ++num;
     }
     xtable[1][x][y] = num;
    }
    else
     prev = false;
    ++x; ++y;
   }
  }
  
  s = 0;
  e = num + 1;
  // make graph
  for (int x = 0; x < n; ++x)
   for (int y = 0; y < n; ++y)
   {
    if (table[x][y] == '.')
    {
     int to1 = xtable[0][x][y];
     int to2 = xtable[1][x][y];
     v[s].push_back(to1);
     v[to1].push_back(to2);
     v[to2].push_back(to1);
     v[to2].push_back(e);
     cap[s][to1] = cap[to1][to2] = cap[to2][e] = 1;
    }
   }
  int res = pushFlow(s, e);
  printf("%d\n", res);
  for (int i = 0; i <= e; ++i)
   v[i].clear();
 }
}
    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    14년 전
10개의 댓글이 있습니다.
  • Toivoa
    Toivoa

    backtracking
    real 1m12.483s
    user 1m12.420s
    sys 0m0.020s
    max-bipartite matching
    real 0m0.967s
    user 0m0.930s
    sys 0m0.000s


    14년 전 link
  • 김우현
    김우현

    ㅠㅠ..;;; 
    정말 후덜덜한 솔루션이네요 ㅠ;
    문제는 검색해보니 2007년도 시도 본선 중등부 5번 문제네요. 참고로 N=100 ㅠ;;
    아래는 참고링크입니다.
    http://lirasoft.tistory.com/?page=177


    14년 전 link
  • Toivoa
    Toivoa

    사실 APC 문제에서 N이 8이었던게 백트래킹을 낚기 위한 것이었습니다.


    14년 전 link
  • Lay
    Lay

    bipartite를 내가 이해 못하고 있는건지... 한글을 덜 깨우친건지...


    14년 전 link
  • JongMan
    JongMan

    birtite 아니죠 bipartite 맞습니다~


    14년 전 link
  • Lay
    Lay

    질문 있습니다. 제가 bipartite를 잘 모르기도 하지만...;
    바이퍼는 일단 두가지 그룹으로 나누고, 그 중 짝이 될 수있는 것들이 연결 되 있는 상태에서, 가장 많은 연결을 하는것이 방법이라고 알고 있는데,
    (혹시 위 내용도 제가 잘못 알고 있다면 지적해주세요)
    그렇다면 여기서는 두가지 그룹은 무엇인지 짝이 될 수 있는 연결 상태는 무엇인지,
    가장 많은 연결 -> 가장 많은 비숍을 구하는 것이 맞는건지 좀 알려주세요;;


    14년 전 link
  • Dynamical
    Dynamical

    최대 이분매칭이 항상 최대값을 구하는 문제에만 국한되어있는 것은 아닙니다.
    최대 이분매칭이 최대 매칭 외에도 여러 방법에 쓰이기도 합니다. 예를 들어서 이분그래프에서 minimum vertex cover를 구할 때도 쓰이고, minimum vertex cover를 구하면 maximum independent set을 구할 수 있기에 이를 구하는 쪽에도 쓰이죠. 대표적으로 헝가리안 메소드를 이분매칭을 이용해서 구할 때 minimum vertex cover를 찾는것과 관련이 있기 때문에 사용하는것이죠...
    이 문제에서는 최대값을 구하는 것과 관련이 있죠. 여기서 일단 한쪽 대각선 방향에 대해서 생각하고 넘버링을 매기면 일단 각 넘버당 많아야 하나의 비숍만 들어갈 수 있습니다.
    이제 우리가 관심있는 것은, 하나의 넘버에 대해서 비숍의 위치가 여러군데가 나오는데, 어떻게 배치해야 가장 많은 비숍을 배치할 수 있냐는 것이죠.
    특정 위치에 배치를 하면, 다른 대각선 방향으로 다른 넘버의 자리와 충돌이 있을 수 있습니다. 따라서 다른 대각선 방향으로 넘버링을 하고 이 넘버링의 집합을 B라 하고, 그 전의 넘버링의 집합을 A라 할 때, 아래와 같은 조건들을 유추할 수 있습니다.
    ㄱ. 임의의 막히지 않은 위치에 대해서, 이 위치에 해당하는 (Ai , Bj)가 정해져 있다.
    (Ai, Bi는 그 위치에 해당하는 A의 원소와 B의 원소를 말함.)
    ㄴ. 동일한 A의 넘버를 가지는 위치들에 대해서, B 넘버는 모두 서로 다르다.
    즉, 어떤 하나의 A 넘버에 대해서 설치할 수 있는 위치들은 여러개의 서로 다른 B 넘버들로 표현할 수 있고,
    만약 (Ai , Bj)에 비숍을 놓는다면 Ai 넘버를 가지는 여러 위치 중 Bj 넘버를 가지는 녀석을 선택한 것이죠. 그리고 A 넘버가 다른 녀석들 중 동일한 Bj 넘버를 가지는 위치에는 (Ai , Bj)의 비숍과 충돌하기 때문에 비숍을 놓을 수 없습니다.
    따라서 각 위치에 대해서 (Ai , Bj)로 표현할 때, 이분그래프를 만들어서 좌측에는 A의 원소, 우측에는 B의 원소를 놓고 Ai -> Bj로 간선을 만들어서 최대 이분매칭을 구하면 그것은 결론적으로 최대 개수의 비숍을 놓는것과 동치가 됩니다.


    14년 전 link
  • Lay
    Lay

    자세한 설명 너무 감사드립니다^^
    하지만, 역시 완벽한 이해를 하기엔 제 능력이 조금 부족하네요.(설명의 부족이 아닙니다!!)
    한번 손으로 그려봐야겠어요 ㅎㅎ


    14년 전 link
  • OneShot
    OneShot

    에고;; 알고리즘을 잘 모르는 저로써는 설명을 읽고도 잘 모르겠네요 ㅎㅎ;; bipartite인가에 대해 좀 더 공부해 봐야 할 것 같습니다. 저는 그냥 직관적으로 문제를 접근해 봤는데요.. 일단
    .*
    **
    이런식으로 주변이 다 막혀있는 경우는 무조건 비숍을 넣을 수 있으니까 카운트 했습니다. 그리고,
    .*
    .
    이런식으로 주변 중 한곳만 뚫려있는(?) 곳도 그 대각선 통틀어 하나만 놓을 수 있기 때문에 /와 가 겹치지 않는 (뚫려있는 곳이 2개 이상이 아닌) 곳도 비숍을 놓는 최대의 경우에 포함하므로 비숍을 넣고 카운트 했습니다. 그 다음엔 그 비숍을 놓음으로 해서 놓을수 없는 곳은 따로 표시를 해 두었고요.. 그렇게 하면 주변이 2곳 이상 뚫려있는 칸만 남게 됩니다. 3곳 이상 뚫린 곳에 넣으면 최대로 비숍을 넣을 수 없으므로(조금만 생각해 보시면 알 수 있습니다.) 2곳이 뚫린 부분을 보면 크게 두가지 패턴이 있다는 것을 알 수 있습니다.
    *.     .
    .*. .
    .
    앞에 것의 첫째줄 빈칸과 뒤에 것의 둘째줄 빈칸이 그것인데요.. 딱 보면 아시겠지만 앞의 것 처럼 /방향과 방향이 겹치는 부분보다는 뒤에것 처럼 한 방향으로만 양쪽으로 뚫린 곳에 넣는 것이 최대로 넣을 수 있는 방법입니다. 비숍을 두고 나면 비숍때문에 못 넣는 위치는 당연히 따로 표시를 해야 할 것이구요. 그리고 다시 그것으로 인해 모든 방향이 막힌 부분과 한쪽 방향만 막히게 되는 것이 있는지 확인해 봐야 합니다. 여기서 주의할 것은
    o..
    .x.
    ..x
    o 표시는 비숍 자리 x 표시는 비숍으로 인해 둘 수 없는 자리 라고 했을 때 첫째줄의 마지막 칸에서 뚫려있는 개수는 1개로 카운트 되어야 하는것입니다. 따라서 장애물 표시(*)와 비숍으로 인해 둘 수 없는 자리(x)는 다르게 표시해 주셔야 합니다. N 이 커지면 모르겠지만 N<=8 인 조건 아래에서는 상당히 빠른 속도를 보여주네요ㅎ


    14년 전 link
  • ILyoan
    ILyoan

    비숍의 특성을 이용하면 이 정도 문제 사이즈는 백트레킹으로도 충분히 풀 수 있습니다.체스판의 검은색 칸에서 시작한 비숍은 항상 검은색 칸 위에서 움직이고 흰색칸 위에 있는 비숍은 항상 흰색칸 위에만 있으므로 흰색칸 위에 있는 비숍과 검은색 칸 위에 있는 비숍간에는 절대로 만나는 일이 없죠. 따라서 이 문제는 사이즈가 절반인 두개의 문제로 치환할 수 있고, 각각의 서브 문제에 대해 백트레킹으로 최대 비숍의 수를 구한 후 두 합을 더하는 것으로 문제를 풀었습니다.
    그나저나 이분매칭으로 푸는 솔루션은 정말 후덜덜이네요


    14년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.