DFS / BFS

nhn pre-test 1차 기출문제

0과 1밖에 없는 N*N 의 행렬이 주어질 때 인접한 1의 영역의 개수, 각 영역의 크기 구하기.

<입력>
첫 째 줄에 행렬의 크기 N이 주어진다.

• 1 <= N <= 10

두 번째 줄부터 N+1줄까지 공백으로 구분된 N개의 0 과 1이 담긴 행렬 정보가 주어진다.

<출력>
첫 번째 줄에 영역의 총 개수를, 두 번 째 줄에 각 영역의 크기를 오름차순으로 공백으로 구분하여 출력. 영역의 개수가 없으면 첫 번째 줄에 0 하나만 출력.

<예시>

6
0 1 1 0 0 0
0 1 1 0 1 1
0 0 0 0 1 1
0 0 0 0 1 1
1 1 0 0 1 0
1 1 1 0 0 0

3
4 5 7

4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

0

---

주어진 코드

#include <iostream>
#include <sstream>

using namespace std;

void solution(int sizeOfMatrix, int **matrix) {
	// todo : 코드를 작성하세요
}

struct input_data
{
    int sizeOfMatrix;
    int **matrix;
};

void process_stdin(struct input_data &inputData)
{
    string line;
    istringstream iss;

    getline(cin, line);
    iss.str(line);
    iss >> inputData.sizeOfMatrix;
    ;

    inputData.matrix = new int *[inputData.sizeOfMatrix];
    for (int i = 0; i < inputData.sizeOfMatrix; i++)
    {
        getline(cin, line);
        iss.clear();
        iss.str(line);
        inputData.matrix[i] = new int[inputData.sizeOfMatrix];
        for (int j = 0; j < inputData.sizeOfMatrix; j++)
        {
            iss >> inputData.matrix[i][j];
        }
    }
}

int main()
{
    struct input_data inputData;
    process_stdin(inputData);

    solution(inputData.sizeOfMatrix, inputData.matrix);
    return 0;
}

---

내가 생각한 답

---

C++

DFS로 풀기

int temp = 0;

bool dfs(int x, int y, int size, int **matrix) {
    if (x < 0 || x >= size || y < 0 || y >= size)
        return false;
    if (matrix[x][y] == 1) {
        matrix[x][y] = 0;
        temp += 1;
        dfs(x - 1, y, size, matrix);
        dfs(x + 1, y, size, matrix);
        dfs(x, y - 1, size, matrix);
        dfs(x, y + 1, size, matrix);
        return true;
    }
    return false;
}

void solution(int sizeOfMatrix, int **matrix) {
    int result = 0;
    int arr[1000];

    for (int i = 0; i < sizeOfMatrix; i++) {
        for (int j = 0; j < sizeOfMatrix; j++) {
            if (dfs(i, j, sizeOfMatrix, matrix) == true) {
                result += 1;
                arr[result - 1] = temp;
                temp = 0;
            }
        }
    }

    sort(arr, arr + result);
    cout << result << endl;
    for (int i = 0; i < result; i++)
        cout << arr[i] << ' ';
}

---

BFS로 풀기

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

int temp = 0;

bool bfs(int x, int y, int size, int **matrix) {
    queue<pair<int, int> > q;

    if (matrix[x][y] == 0) {
        return false;
    }
    if (matrix[x][y] == 1) {
        matrix[x][y] = 0;
        temp += 1;
        q.push(make_pair(x, y));
        while (!q.empty()) {
            x = q.front().first;
            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 >= size || ny < 0 || ny >= size) {
                    continue;
                }
                if (matrix[nx][ny] == 0) {
                    continue;
                }
                if (matrix[nx][ny] == 1) {
                    matrix[nx][ny] = 0;
                    q.push(make_pair(nx, ny));
                    temp += 1;
                }
            }
        }
    }
    return true;
}

void solution(int sizeOfMatrix, int **matrix) {
    int result = 0;
    vector<int> arr;

    for (int i = 0; i < sizeOfMatrix; i++) {
        for (int j = 0; j < sizeOfMatrix; j++) {
            if (bfs(i, j, sizeOfMatrix, matrix) == true) {
                arr.push_back(temp);
                result += 1;
                temp = 0;
            }
        }
    }
    sort(arr.begin(), arr.end());
    cout << result << endl;
    for (int i = 0; i < result; i++) {
        cout << arr[i] << ' ';
    }
}

Python

DFS

n = int(input())
graph = []
copy_graph = []
for _ in range(n):
    graph.append(list(map(int, input())))


temp = 0
arr = []

def dfs(x, y):
    if x<0 or x>=n or y<0 or y>=n:
        return 0
    if graph[x][y] == 1:
        graph[x][y] = 0
        global temp
        temp += 1
        dfs(x-1, y)
        dfs(x+1, y)
        dfs(x, y-1)
        dfs(x, y+1)
        return 1
    return 0
    
    

result = 0
arr = []
for x in range(n):
    for y in range(n):
        if dfs(x,y) != 0:
            result += 1
            arr.append(temp)
            temp = 0            

print(result)
print(arr)

BFS

코드를 입력하세요