BFS

학부 때 이후로 오랜만에 BFS를 사용했다.

 

격자에서 영역을 구할 때 사용하였다.

 

이해한 대로 PPT를 이용하여 간단하게 그려보았다.

 

기본 원리는 주변을 살펴서 내 그룹이고, 방문 안했으면 queue에 넣고, 다 확인하면 queue에서 다음 것을 빼내어 똑같이 하는 것이다.

 

학부때는 이걸 재귀함수로 했던것 같은데, queue로 하는게 더 쉬운것 같다.

 

queue에 pair를 사용했는데, 행렬을 각각 넣기 위해서 그랬다.

 

for(int i=0; i<m; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(palette[i][j] != 0)
            {
                if(visit[i][j] == false)
                {
                    int color = palette[i][j];
                    int num = 1;
                    q.push(make_pair(i, j));
                    visit[i][j] = true;
                    number_of_area++;
                    
                    while(!q.empty())
                    {
                        x = q.front().first;
                        y = q.front().second;
                        q.pop();
                        
                        for(int k=0; k<4; k++)
                        {
                            int nx = x + dx[k];
                            int ny = y + dy[k];
                            
                            if(0 <= nx && nx < m && 0 <= ny && ny < n)
                            {
                                if(palette[nx][ny] == color && visit[nx][ny] == false)
                                {
                                    visit[nx][ny] = true;
                                    num++;
                                    q.push(make_pair(nx, ny));
                                }
                            }
                        }
                    }
                }
            }
        }
    }

 

문제는 다음과 같이 구현해서 풀었다.

 

이때, dx,dy는

    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};

로 미리 설정하여 상하좌우를 확인하도록 하였다.

 

알고리즘 문제에서 생각보다 자주 나온다니 DFS와 같이 잘 기억해두는게 좋겠다.