[Algorithm] Baekjoon 1652번 : 누울 자리를 찾아라

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

1652번: 누울 자리를 찾아라

struct Node
{
    int y;
    int x;
    int count;
    int dir;
};
 
int widthCount = 0;
int heightCount = 0;
char arr[101][101];
int n;
int visited[2][101][101] = { false };
int dir[2][2] = { {0,1}, {1,0} };
 
void BFS(int startY, int startX)
{
    queue<Node> q;
 
    visited[0][startY][startX] = true; 
    q.push({ startY,startX,1,0 }); // 가로
 
    if (!visited[1][startY][startX]) // 세로
    {
        visited[1][startY][startX] = true; 
        q.push({ startY,startX,1,1 });
    }
        
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        int curCount = q.front().count;
        int curDir = q.front().dir;
        q.pop();
 
        int nextY = curY + dir[curDir][0];
        int nextX = curX + dir[curDir][1];
 
        if (curDir == 0) // 가로로 뻗어가던 노드면
        {
            if (nextX < n && arr[nextY][nextX] != 'X' && !visited[0][nextY][nextX])
            {
                visited[0][nextY][nextX] = true;
                q.push({ nextY,nextX,curCount + 1,0 });
 
                visited[1][nextY][nextX] = true;
                q.push({ nextY,nextX,1,1 });
            }
            else // 벽이거나, 끝이거나
            {
                if (curCount >= 2) ++widthCount;
            }
        }
        else // 세로로 뻗어가던 노드면
        {
            if (nextY < n && arr[nextY][nextX] != 'X' && !visited[1][nextY][nextX])
            {
                visited[1][nextY][nextX] = true;
                q.push({ nextY,nextX,curCount + 1,1 });
            }
            else
            {
                if (curCount >= 2) ++heightCount;
            }
        }
    }
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (visited[0][i][j] || arr[i][j] == 'X') continue;
            BFS(i, j);
        }
    }
 
    cout << widthCount << ' ' << heightCount;
}

 

사실 BFS를 안해도 되는 문제이긴 하다. 어차피 오른쪽,아래만 검사하면 되기 때문.

다만 굳이 BFS로 한 이유는, 내가 생각한대로 구현 잘 되는지를 연습하기위함이다.

가로 검사할 때 세로까지 한꺼번에 검사할 수 있는 방법이 있고, 그걸 코드로 구현해봤다.

 

기본적으로 가로로 검사하는 BFS이기 때문에, 노드가 우측방향(가로방향)의 노드면 가는길에 아래방향으로 노드를 하나씩 뿌려준다. 해당노드들은 알아서 끝까지 아래로 내려간다음 조건에 맞으면 카운팅을 한다.

노드가 아랫방향이면 그냥 아랫방향으로만 간다. main에서 우측에 대해서 다 돌리기 때문에 아랫방향에서 우측방향노드를 뿌릴필요는 없다.