Softeer Lv2. 장애물 인식 프로그램

백준 2667 단지 번호 붙이기와 같은 문제

문제풀이 링크

완전히 같은 문제이나, IDE를 사용하지 않고 풀이에 도전

주의점

• IDE를 사용하지 않으므로 디버깅이 힘들다
• 여기저기서 Printf를 통해 디버깅 시도
• BFS 함수 내에서 visited를 선언했더니, 초기화가 제대로 되지 않아 굉장히 헤맸음
  • 출력시에는 0으로 잘 출력되어 문제가 없는줄 알았으나 일부 TC를 통과하지 못했음
  • 결국 IDE에서 돌려보고나서 뭐가 문젠지 확인했음
• 줄입력으로 들어오므로, 이를 잘라서 int형으로 셀마다 저장해야함

3. 소스코드

---

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int N;
int map[26][26];

struct node{
  int y;
  int x;
};
int direct[4][2] = {0,-1,-1,0,0,1,1,0}; // 4방향
vector<int> result;

void PrintMap(){
  cout << "============== Map ==============" <<endl;
  for(int y=0; y<N; y++){
    for(int x=0; x<N; x++){
      cout << map[y][x];
    }
    cout << endl;
  }
}

void BFS(int y, int x){
  int visited[26][26] = {0};
  queue<node> qu;

  // 첫 노드 방문처리
  visited[y][x] = 1;
  map[y][x] = 0;  

  // 큐에 넣음
  qu.push({y, x});
  int size = 0;
  
  while(!qu.empty()){
    node now = qu.front();
    qu.pop();

    size++;
    
    for(int t=0; t<4; t++){
      int dy = direct[t][0] + now.y;
      int dx = direct[t][1] + now.x;

      if(dy < 0 || dx < 0 || dy >= N || dx >= N) continue;
      if(map[dy][dx] == 0) continue; // 바다라면 패스
      if(visited[dy][dx] == 1) continue; // 이미 방문 배열은 패스

      visited[dy][dx] = 1;
      map[dy][dx] = 0; 
      qu.push({dy, dx}); 
    }
  }  
  result.push_back(size);

}

int main(int argc, char** argv)
{
  cin >> N;
  for(int y=0; y<N; y++){
    string tmp; cin >> tmp;
    for(int x=0; x<tmp.size(); x++){
      map[y][x] = tmp[x] - '0';
    }
  }

  int cnt=0;
  for(int y=0; y<N; y++){
    for(int x=0; x<N; x++){
      if(map[y][x] == 1){
        BFS(y, x);
        cnt++;
      }
    }
  }
  
  cout << cnt << endl;

  // 오름차순으로 정렬
  sort(result.begin(), result.end());
  
  for(auto e : result){
    cout << e << endl;
  }
   return 0;
}