[C++] BOJ1926 (BFS의 구현)

[Settpark]

• 그림의 수를 Num, 최대 크기를 mx로 두고 알고리즘을 풀었는 데,

• Queue에 값을 넣을 때마다 단순히 mx++를 진행하였다. mx는 연속해서 진행 되는 것이 아님에도 (새로운 그림에 들어갈 때마다 초기화 해주어야 한다.)

• 잘못된 코드

    int num = 0, mx = 0;
    
    for (int i = 0; i < width; i++)
        for (int j = 0; j < height; j++)
            cin >> board[i][j];
    
    for (int i = 0; i < width; i++) {
        for (int j = 0; j < height; j++) {
            if (vis[i][j] || board[i][j] == 0) continue;
            num++;
            queue<pair<int, int>> Q;
            vis[i][j] = 1;
            Q.push({i,j});
            while(!Q.empty()) {
                area++;
                pair<int, int> cur = Q.front(); Q.pop();
                
                for (int dir = 0; dir < 4; dir++) {
                    int nx = cur.first + dx[dir];
                    int ny = cur.second + dy[dir];
                    
                    if (nx > width || nx < 0 || ny > height || ny < 0) continue;
                    if (vis[nx][ny] || board[nx][ny] != 1) continue;
                    vis[nx][ny] = 1;
                    Q.push({nx,ny});
                    mx++; // 해당 부분이 잘못 되었다. BFS의 시작점을 제외하곤 모두 ++를 하게 된다. 
                }
            }
        }
    }

• 올바른 코드

    for (int i = 0; i < width; i++)
        for (int j = 0; j < height; j++)
            cin >> board[i][j];
    
    for (int i = 0; i < width; i++) {
        for (int j = 0; j < height; j++) {
            if (vis[i][j] || board[i][j] == 0) continue;
            num++;
            queue<pair<int, int>> Q;
            vis[i][j] = 1;
            Q.push({i,j});
            int area = 0; // BFS가 새로 시작될 때마다 새로운 변수를 주고,
            while(!Q.empty()) {
                area++; //pop할때마다 area를 크기를 늘리면 된다.
                pair<int, int> cur = Q.front(); Q.pop();
                
                for (int dir = 0; dir < 4; dir++) {
                    int nx = cur.first + dx[dir];
                    int ny = cur.second + dy[dir];
                    
                    if (nx > width || nx < 0 || ny > height || ny < 0) continue;
                    if (vis[nx][ny] || board[nx][ny] != 1) continue;
                    vis[nx][ny] = 1;
                    Q.push({nx,ny});
                }
            }
            mx = max(mx, area); //BFS가 끝나게 되면 area와 현재의 최댓값을 비교하여 큰 값으로 갱신한다.
        }
    }