[소프티어] 장애물 인식 프로그램 (C++)

👓 문제 설명

---

자율주행팀 SW 엔지니어인 당신에게 장애물과 도로를 인식할 수 있는 프로그램을 만들라는 업무가 주어졌다.

[그림 1] 지도 예시

우선 [그림 1]과 같이 정사각형 모양의 지도가 있다. 1은 장애물이 있는 곳을, 0은 도로가 있는 곳을 나타낸다.

당신은 이 지도를 가지고 연결된 장애물들의 모임인 블록을 정의하고, 불록에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 장애물이 좌우, 혹은 아래위로 붙어 있는 경우를 말한다. 대각선 상에 장애물이 있는 경우는 연결된 것이 아니다.

[그림 2] 블록 별 번호 부여

[그림 2]는 [그림 1]을 블록 별로 번호를 붙인 것이다.

지도를 입력하여 장애물 블록수를 출력하고, 각 블록에 속하는 장애물의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

---

💣 제한 사항

• N은 정사각형임으로 가로와 세로의 크기는 같으며 5 ≤ N ≤ 25
• 입력 값의 첫 번째 줄에는 지도의 크기 N이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

---

🚨 접근 방법

장애물의 총 개수 그리고 이어진 장애물의 개수를 구해야한다.
이런 경우 BFS가 아닌 DFS가 더 효율적이다.
그러나 입력에서 문제가 있었다.
cin으로 받을 경우 예제처럼 첫번째 행이 1110111인경우
cin >> arr[i][j]을 해버리면 arr[i][j]에 한 행의 값이 전부 들어간다.
그래서 문자열로 받은 후 아스키코드 값 이용하여 한 공간에 하나의 숫자를 넣었다.

---

🚈 풀이

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#define MAX 25
using namespace std;
bool visited[MAX][MAX];
int arr[MAX][MAX];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int n,cnt=0,cnt1=0;

void dfs(int x,int y){
  cnt++;
  visited[x][y]=true;
  for(int i=0;i<4;i++){
    int next_x=x+dx[i];
    int next_y=y+dy[i];
    if(next_x>=0&&next_x<n&&next_y>=0&&next_y<n){
      if(arr[next_x][next_y]==1&&!visited[next_x][next_y]){
        dfs(next_x,next_y);
      }
    }
  }
}

int main(int argc, char** argv)
{
  // 입력을 받고 장애물이 있는 지점을 전부 저장한다.
  // dfs를 통해 장애물이 있는 지점을 탐색한다.
  // ex) 장애물이 있는 배열의 첫번째 원소를 dfs하면 이미 방문한 지점은 다시 방문을 안할것이다.
  // 모든 원소에 대해 dfs를 하고 dfs를 실행하는 경우 cnt를 센다.

  vector<int>answer;
  string s;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>s;
    for(int j=0;j<n;j++){
      arr[i][j]=s[j]-'0';
    }
  }

  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(arr[i][j]==1&&!visited[i][j]){
        visited[i][j]=true;
        dfs(i,j);
        answer.push_back(cnt);
        cnt=0;
        cnt1++;
      }
    }
  }
  
  cout<<cnt1<<"\n";
  sort(answer.begin(),answer.end());
  
  for(auto p:answer){
    cout<<p<<"\n";
  }
  
   return 0;
}