단지번호붙이기 [C++]

문제 링크: https://www.acmicpc.net/problem/2667

난이도: ⚪

문제 설명

문제 접근

1. 인접행렬로 구성된 그래프에서 상하좌우를 확인하여 연결되어있는지 확인한다.
2. 집(1)을 방문시 방문기록이 없다면, 그 집을 시작으로 BFS를 실행한다.
   • BFS 실행시 집을 방문할 때 마다 개수를 세주면 BFS가 끝날때 단지가 완성된다.
3. 단지수를 오름차순으로 정렬하여 출력한다.
   
   

제출 코드

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

// 지도 map, 방문 위치 visited, 단지수를 저장한 answer
vector<int> map[25]{};
bool visited[25][25];
vector<int> answer;

// BFS 구현
void BFS(int x, int y, int n)
{
	// 집의 수 
    int cnt = 1;
    visited[x][y] = true;
    queue<pair<int, int>> q; 
    q.push({ x, y });
	
    // 방향을 나타낸 행렬
    int dx[4] = { 0, 0, -1, 1 };
    int dy[4] = { -1, 1, 0, 0 };

    while (!q.empty())
    {
        int cur_x = q.front().first;
        int cur_y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = dx[i] + cur_x;
            int ny = dy[i] + cur_y;
            // 탐색 위치가 인덱스 범위를 벗어나지 않도록 제한한다.
            if (nx > -1 && ny > -1 && nx < n && ny < n && map[nx][ny] == 1)
            {
            	// 방문한 지역이 아닐 경우 기록을 남기고 카운트한다.
                if (visited[nx][ny] == false)
                {
                    q.push({ nx, ny });
                    visited[nx][ny] = true;
                    cnt++;
                }
            }
        }
    }
    // BFS가 끝날때 한 단지가 완성되기 때문에 answer 벡터에 집의 개수를 넣어주면 끝. 
    answer.push_back(cnt);
}

int main(void)
{
    int N;
    cin >> N;
    string temp;
    
    // 지도 초기화.
    for (int i = 0; i < N; i++)
    {
        cin >> temp;

        for (int j = 0; j < N; j++)
            map[i].push_back(temp[j] - '0');
    }
    
    // 방문 기록이 없고 집이 있는 곳이면 BFS탐색을 실시한다.
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
            if (visited[i][j] == false && map[i][j] == 1)
                BFS(i, j, N);
    }
    
    // 오름차순으로 정렬
    sort(answer.begin(), answer.end());

	// 총 단지의 수(answer 벡터의 길이)와 정렬된 단지(집의 개수)들을 출력한다.
    cout << answer.size() << '\n';
    for (int i = 0; i < answer.size(); i++)
        cout << answer[i] << '\n';

    return 0;
}

실수한 부분

처음 문제를 접근했을 때 몇가지 실수가 있었다.

• 첫 번째는 BFS부분에서 방문한 지역이 아닐 경우 queue에 push를 해주고 방문기록을 남겨야 하는데 기록을 남기지 않아 집들이 개별적으로 저장되었다.
• 두 번째는 BFS구현에서 nx와 ny를 현재 큐에서 뽑아온 값을 사용했어야 했는데 함수의 매개변수로 받아온 값을 사용해 오류가 있었다.
• 세 번째는 BFS탐색을 실행하는 조건에서 map[i][j]위치에 집이 존재하는지 확인하는 부분이 빠져있었다.

탐색하는 과정과 탐색을 실시하는 조건을 좀더 꼼꼼하게 만들어줘야 될 것 같다.

결과