[boj][c++] 14502 연구소

14502 연구소

그래프 크기가 8*8이라서 모든 조합을 판단했을 때 (최대 64개 노드 중 값이 2인 노드 최소 2개 이상) 62*61*60개 경우의 수를 갖는다.

처음에 문제에 대한 접근을 떠올리지 못한 이유는 bfs/dfs의 시간복잡도가 O(N^2)인데 n과 m이 최대값인 8이라고 가정할 때 O((n*m)^2)이므로 위의 경우의 수를 모두 bfs하게 되면 929,464,320의 연산을 수행해야 한다. 계산이 잘못된 것일수도 있지만 문제에 접근하기 전 완전탐색을 생각했을 때 이런 생각으로 인해 섣불리 시작하지 못했다. 9억회 연산은 시간초과일거라 생각했다.

• 그래프를 입력받은 뒤에 값이 0인 임의의 노드를 1로 바꾸고 wall함수를 실행시킨다. 노드의 값은 다시 0으로 바꾼다.
  • (wall함수)
  • 수정되는 노드가 세개가 되면 bfs를 실행하여 값이 2인 노드의 인접노드를 2로 바꾼다
  • 인접노드를 2로 변경한 뒤 값이 0인 노드의 개수를 구한다
• 이 과정을 모든 경우의 수만큼 실행한다

조합, bfs가 쓰인 문제였다. 처음 문제를 접했을 때 간단히 구현할 수 있을 것 같다고 느꼈으나 실제로 구현하면서 어려움을 많이 겪었다. 배열과 좌표평면에 대한 이해 부족으로 x와 y를 혼동해서 꽤 많은 시간을 잡아먹었다. 힝...

<수정전>

#include    <iostream>
#include	<cstring>
#include    <algorithm>
#include    <queue>
using namespace std;

//그래프배열
int n,m,ans;
int graph[8][8];
bool visit[8][8];
int temp[8][8];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};

//조합
void wall(int n)
{
    if(n==3)
    {
        bfs();
        return;
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(temp[i][j]==0)
            {
                temp[i][j]=1;
                wall(n+1);
                temp[i][j]=0;
            }
        }
    }
}

//bfs
void bfs(void)
{
    int ans[8][8];
    copy(ans,temp);
    queue<pair<int,int>> q;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(ans[i][j]==2)
                q.push({i,j});
        }
    }
    while(!q.empty())
    {
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        for(int i=0;i<4;i++)
        {
            int nx=x+dx[i];
            int ny=y+dy[i];
            if((nx>=0&&nx<n)&&(ny>=0&&ny<m))
            {
                if(ans[nx][ny]==0)
                {
                    ans[nx][ny]=2;
                    q.push({nx,ny});
                }
            }
        }
    }
    int cnt=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(ans[i][j]==0)
                cnt++;
        }
    }
    ans = max(ans,cnt);
}

//그래프복사배열
void copy(int temp[8][8],int graph[8][8])
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            temp[i][j]=graph[i][j];
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
            cin>>graph[i][j];
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;i++)
        {
            if(graph[i][j]==0)
            {
                memset(visit,0,sizeof(visit));
                copy(temp,graph);
                temp[i][j]=1;
                wall(1);
                temp[i][j]=0;
            }
        }
    }
    
}

<수정후>

#include    <iostream>
#include    <algorithm>
#include    <queue>
using namespace std;

int n, m, answ;
int graph[8][8];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

void bfs(void)
{
    int graph_copy[8][8] = { 0, };
    queue<pair<int, int>> q;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            graph_copy[i][j] = graph[i][j];
            if (graph[i][j] == 2)
            {
                q.push({ i,j });
            }
        }
    }
    while (!q.empty())
    {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (((nx >= 0 && nx < m) && (ny >= 0 && ny < n)) && graph_copy[ny][nx] == 0)
            {
                graph_copy[ny][nx] = 2;
                q.push({ ny,nx });
            }
        }
    }
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (graph_copy[i][j] == 0)
                cnt++;
        }
    }
    answ = max(answ, cnt);
    return;
}

void wall(int num)
{
    if (num == 3)
    {
        bfs();
        return;
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (graph[i][j] == 0)
            {
                graph[i][j] = 1;
                wall(num + 1);
                graph[i][j] = 0;
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            cin >> graph[i][j];
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (graph[i][j] == 0)
            {
                graph[i][j] = 1;
                wall(1);
                graph[i][j] = 0;
            }
        }
    }
    cout << answ;
}