[Algorithm]Baekjoon 14466번 :: 소가 길을 건너간 이유 6

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

14466번: 소가 길을 건너간 이유 6

struct Node
{
    int y;
    int x;
};
 
int n, k, r;
 
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
vector<Node> cowsInfo;
int arr[101][101];
bool dirCheck[101][101][4] = { false };
int answer = 0;
 
void BFS(int startIndex)
{
    memset(arr, 0, sizeof(arr));
 
    for (int i = startIndex+1; i < cowsInfo.size(); ++i)
    {
        Node cow = cowsInfo[i];
        arr[cow.y][cow.x] = 2;
    }
 
    queue<Node> q;
    Node startNode = { cowsInfo[startIndex].y, cowsInfo[startIndex].x };
    q.push({ startNode.y, startNode.x });
    arr[startNode.y][startNode.x] = 1;
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        q.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            if (dirCheck[curY][curX][i]) continue; // 해당 길로 이동할 수 있으면 x.
            
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY >= n) continue;
            if (nextX < 0 || nextX >= n) continue;
            if (arr[nextY][nextX] == 1) continue;
 
            if (arr[nextY][nextX] == 2)
            {
                ++answer;
            }
 
            arr[nextY][nextX] = 1;
            q.push({ nextY,nextX });
        }
    }
}
 
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> k >> r;
 
    for (int i = 0; i < r; ++i)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
 
        if (c - a == 0) // y값 같으면
        {
            if (d - b == 1) // a,b가 c,d의 왼쪽에 있다면
            {
                dirCheck[a-1][b-1][3] = true;
                dirCheck[c-1][d-1][2] = true;
            }
            else // d- b == -1
            {
                dirCheck[a-1][b-1][2] = true;
                dirCheck[c-1][d-1][3] = true;
            }
        }
        else if (d - b == 0) // x값이 같으면
        {
            if (c - a == 1) // c,d가 a,b보다 아래에 있다면
            {
                dirCheck[a-1][b-1][1] = true;
                dirCheck[c-1][d-1][0] = true;
            }
            else
            {
                dirCheck[a-1][b-1][0] = true;
                dirCheck[c-1][d-1][1] = true;
            }
        }
    }
 
    int allPairNum = ((1 + k - 1) * (k-1)) / 2;
 
    for (int i = 0; i < k; ++i)
    {
        int a, b;
        cin >> a >> b;
        cowsInfo.push_back({ a-1,b-1 });
    }
 
    for (int i = 0; i < cowsInfo.size(); ++i)
    {
        BFS(i);
    }
 
    cout << allPairNum - answer;
 
    return 0;
}

문제설명이 애매해서 다른 사람글을 봤더니 다른 사람들도 설명이 애매하다고 글마다 쓰여있다 ㅋㅋㅋ;;;

 

간단히 말하면, 주어진 길을 이용해야만 다른 소에게 갈 수 있는 경우의 수를 구하는 문제다.

 

즉, 거꾸로 말하면 전체 경우의 수에서 '길을 이용하지않고도 다른 소에게 갈 수 있는 경우의 수'를 빼서 출력하면 된다.

 

여기서 헷갈리지 말아야할 것은, 전체 경우의 수란 전체 소의 마릿수가 아니다.

 

각 소가 서로에게 닿을 수 있는 가짓수이다. 그리고 첫번째소가 두번째소에게 닿는거와 두번째소가 첫번째소에게 닿는것은 같은걸로 카운팅하기 때문에, 전체 경우의 수는 등비수열의 합으로 구했다.

 

ex) 소가 5마리라면 1부터 4까지 합친 결과와 같다. 

     첫번째 소는 2,3,4,5번째 소와 쌍이 될 수 있고 두번째 소는 3,4,5번째 소와 쌍이 될 수 있다. 1번째 소는 이미 그전에 검사했기 때문에 제외한다.

그러면 결국 소가 5마리라면 4 + 3 + 2 + 1.... 등비가 1인 등비수열의 합이 된다. 그러니 1부터 k-1까지 등비수열의합 공식을 적용하면 된다.

 

그리고 BFS탐색을 통해 길을 이용하지 않으면서 다른 소에게 갈 수 있는 경우의 수를 구한다.

주어진 길에 대한 정보같은 경우, 나는 visited를 3차원으로 선언해서 표시했다.

visited[n][n][4] 인데, n,n에서 상,하,좌,우로 이동할 수 있는지 없는지를 체크한다.

상하좌우가 각각 인덱스 0,1,2,3 에 대응 되며, visited[3][3][2] == true 일 경우 3,3에서 좌측으로 이동할 수 없다는 뜻이다.

 

그래서 각 방향으로의 next좌표를 구할 때, 미리 visited체크를 통해 해당방향으로 갈 수 없으면 해당 방향으로의 next값을 구하지 않는다. 이런식으로 진행하다가 next좌표가 소일 경우, 카운팅을 해준다.

그리고 조심해야할 것은 다른 소를 만나서 카운팅 해준다음 해당 좌표도 큐에 push해줘야 한다는 것이다.

다른 문제에서는 보통 특정타겟을 만나면 continue하는 경우가 많아서 습관처럼 그렇게 했다가 틀렸다고 나와서 조금 고민했었다. 

다른 소를 만나더라도 해당좌표에서 또 이동을 해야 하니 큐에 넣는걸 잊지말자