홈 [C++] softeer Level2 장애물 인식 프로그램
포스트
취소

[C++] softeer Level2 장애물 인식 프로그램

게시 2023/07/27
By dapin
12 분읽는 시간

Table of Contents

문제

정사각형인 2차원 배열이 주어진다. 0은 도로이고 1은 장애물이니 각 장애물마다 칸 수를 세고, 장애물의 개수와 오름차순으로 정렬한 각 장애물 당 칸 수를 출력하라.

계획

이거 구역 나눠서 색칠하기 문제잖아. 라벨 번호를 정하는 함수와 재귀를 돌면서 그 라벨을 붙이는 함수로 분리하면 돼.

  • 라벨 번호 정하는 함수가 먼저 배열을 돌면서 장애물을 찾고, 하나 발견되면 라벨 붙이기 시작.
  • 라벨 붙이는 함수는 호출된 자리에 라벨을 붙인 후 상하좌우에 붙어있는 장애물이 있는지 보고 있는 부분에만 재귀 호출. 재귀 수를 줄이기 위해 장애물이 맞는지 먼저 확인하고 호출.

근데 사실 라벨을 굳이 붙일 필요까지는 없고 개수만 세면 되니까 라벨은 빼고 전부 -1로 통일하자. 이 칸을 확인했는지 안했는지만 구분할 수 있으면 돼. 재귀로 만들어서 성공하면 반복으로도 만들어보고.

코드

문제의 입력 사이즈가 작아 각 코드의 실행 시간은 별로 차이나지 않는다. 참조 변수로 전달받은 값들은 전역 변수로 생성해도 똑같이 기능할 수 있다. 그냥 내가 main 바깥에 변수를 두는 걸 별로 좋아하지 않아서 참조 변수를 썼을 뿐이다. 전역 변수 아무데나 쓰면 관리가 안 되잖아. 물론 static을 써도 같은 기능은 하지만 이건 안 쓰던 거라 더 못다루기도 하고, 꼭 필요하지는 않아서 안 썼다.

원래 제출할 때는 재귀 호출 부분에서 반복문과 switch를 썼는데, 코드 정리하다 보니 그게 필요가 없어서 수정했다. 괜한 짓을 했더라.

우선순위 큐는 아무래도 정렬 하면 우선순위 큐지 하는 생각이 있어서 쓴 건데 이 문제에서는 굳이 항상 정렬되어 있을 필요는 없고 나중에 몰아서 정렬해도 되니까 그냥 배열을 쓰고 한번에 정렬하는 게 낫더라. 제출된 결과에서는 별 차이가 안 나고 디버깅 돌리면 아주 약간 시간이 단축된다. 몇 ms 정도.

재귀와 우선순위 큐

  • void find_obstacle(): 배열 크기, 배열, 우선순위 큐를 전달받아 장애물을 찾기 시작한다. 우선순위 큐는 각 장애물의 칸 수를 저장한다. 칸 수를 오름차순으로 정렬하기 위해 사용. 일부 파라미터는 다른 곳에서도 사용하기 위해 참조 변수로 전달받는다.
  • void color_obstacle(): 배열 크기, 배열, 좌표, 장애물 칸 수를 전달받아 장애물을 확인하고 수를 센다. 인접한 같은 장애물을 발견하면 재귀 호출한다. 일부 파라미터는 static처럼 사용하기 위해 참조 변수로 전달받는다.
  • main: 배열을 입력받고, 장애물 칸 수를 저장할 우선순위 큐를 생성해 함수를 호출한 후 돌아온 결과를 출력한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

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

void color_obstacle(int n, vector<vector<int>>& mat, int x, int y, int& num_obs) {
  mat[x][y] = -1;

  if (x - 1 >= 0 && mat[x - 1][y] == 1) color_obstacle(n, mat, x - 1, y, ++num_obs);
  if (y - 1 >= 0 && mat[x][y - 1] == 1) color_obstacle(n, mat, x, y - 1, ++num_obs);
  if (x + 1 < n && mat[x + 1][y] == 1) color_obstacle(n, mat, x + 1, y, ++num_obs);
  if (y + 1 < n && mat[x][y + 1] == 1) color_obstacle(n, mat, x, y + 1, ++num_obs);

  return;
}

void find_obstacle(int n, vector<vector<int>>& mat, priority_queue<int, vector<int>, greater<int>>& obs) {
  int num_obs = 0;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (mat[i][j] == 1) {
        num_obs = 0;
        color_obstacle(n, mat, i, j, ++num_obs);
        obs.emplace(num_obs);
      }
    }
  }

  return;
}

int main()
{
  // 빠른 입출력
  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

  vector<vector<int>> mat;
  priority_queue<int, vector<int>, greater<int>> obs;
  int n, temp;
  string line;

  cin >> n;

  for (int i = 0; i < n; i++) {
    mat.emplace_back(vector<int>());
    cin >> line;
    for (char c : line) {
      mat[i].emplace_back(c - '0');
    }
  }

  find_obstacle(n, mat, obs);

  cout << obs.size() << "\n";

  while (!obs.empty()) {
    temp = obs.top();
    obs.pop();
    cout << temp << "\n";
  }

  return 0;
}

재귀와 정렬

  • void find_obstacle(): 배열 크기, 장애물 배열, 장애물 칸 수 배열을 전달받아 장애물을 찾기 시작한다. 일부 파라미터는 다른 곳에서도 사용하기 위해 참조 변수로 전달받는다.
  • void color_obstacle(): 배열 크기, 장애물 배열, 좌표, 장애물 칸 수를 전달받아 장애물을 확인하고 수를 센다. 인접한 같은 장애물을 발견하면 재귀 호출한다. 일부 파라미터는 static처럼 사용하기 위해 참조 변수로 전달받는다.
  • main: 배열을 입력받고, 장애물 칸 수 배열을 생성해 함수를 호출한 후 돌아온 결과를 정렬하여 출력한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

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

void color_obstacle(int n, vector<vector<int>>& mat, int x, int y, int& num_obs) {
  mat[x][y] = -1;

  if (x - 1 >= 0 && mat[x - 1][y] == 1) color_obstacle(n, mat, x - 1, y, ++num_obs);
  if (y - 1 >= 0 && mat[x][y - 1] == 1) color_obstacle(n, mat, x, y - 1, ++num_obs);
  if (x + 1 < n && mat[x + 1][y] == 1) color_obstacle(n, mat, x + 1, y, ++num_obs);
  if (y + 1 < n && mat[x][y + 1] == 1) color_obstacle(n, mat, x, y + 1, ++num_obs);

  return;
}

void find_obstacle(int n, vector<vector<int>>& mat, vector<int>& obs) {
  int num_obs = 0;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (mat[i][j] == 1) {
        num_obs = 0;
        color_obstacle(n, mat, i, j, ++num_obs);
        obs.emplace_back(num_obs);
      }
    }
  }

  return;
}

int main()
{
  // 빠른 입출력
  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

  vector<vector<int>> mat;
  vector<int> obs;
  int n;
  string line;

  cin >> n;

  for (int i = 0; i < n; i++) {
    mat.emplace_back(vector<int>());
    cin >> line;
    for (char c : line) {
      mat[i].emplace_back(c - '0');
    }
  }

  find_obstacle(n, mat, obs);
  sort(obs.begin(), obs.end());

  cout << obs.size() << "\n";

  for (int i = 0; i < obs.size(); i++) {
    cout << obs[i] << "\n";
  }

  return 0;
}

반복과 정렬

  • void find_obstacle(): 배열 크기, 장애물 배열, 장애물 칸 수 배열을 전달받아 장애물을 찾기 시작한다. 일부 파라미터는 다른 곳에서도 사용하기 위해 참조 변수로 전달받는다.
  • int color_obstacle(): 배열 크기, 장애물 배열, 좌표를 전달받아 장애물을 확인하고 수를 센다. 스택을 이용해 재귀 호출을 대체한다. 장애물 칸 수를 반환한다.
  • main: 배열을 입력받고, 장애물 칸 수 배열을 생성해 함수를 호출한 후 돌아온 결과를 정렬하여 출력한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

int color_obstacle(int n, vector<vector<int>>& mat, int x, int y) {
  stack<pair<int, int>> call_stack;
  pair<int, int> temp;
  int num_obs = 0;

  call_stack.emplace(x, y);

  while (!call_stack.empty()) {
    temp = call_stack.top();
    call_stack.pop();
    x = temp.first;
    y = temp.second;

    if (mat[x][y] == 1) {
      mat[x][y] = -1;
      num_obs++;
    }

    if (x - 1 >= 0 && mat[x - 1][y] == 1) call_stack.emplace(x - 1, y);
    if (y - 1 >= 0 && mat[x][y - 1] == 1) call_stack.emplace(x, y - 1);
    if (x + 1 < n && mat[x + 1][y] == 1) call_stack.emplace(x + 1, y);
    if (y + 1 < n && mat[x][y + 1] == 1) call_stack.emplace(x, y + 1);
  }

  return num_obs;
}

void find_obstacle(int n, vector<vector<int>>& mat, vector<int>& obs) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (mat[i][j] == 1) {
        obs.emplace_back(color_obstacle(n, mat, i, j));
      }
    }
  }

  return;
}

int main()
{
  // 빠른 입출력
  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

  vector<vector<int>> mat;
  vector<int> obs;
  int n;
  string line;

  cin >> n;

  for (int i = 0; i < n; i++) {
    mat.emplace_back(vector<int>());
    cin >> line;
    for (char c : line) {
      mat[i].emplace_back(c - '0');
    }
  }

  find_obstacle(n, mat, obs);
  sort(obs.begin(), obs.end());

  cout << obs.size() << "\n";

  for (int i = 0; i < obs.size(); i++) {
    cout << obs[i] << "\n";
  }

  return 0;
}
IT, 문제풀이
지식 IT 문제풀이 softeer
이 기사는 저작권자의 CC BY-NC-ND 4.0 라이센스를 따릅니다.
최근 업데이트
바로가기