[백준 C++ 2667번] 단지 번호 붙이기

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

---

이해하기 

문제점 1 : 입력 받기

유기농 배추 문제랑 매우 유사했던 문제였다.  (풀이 https://xoxoxoxox.tistory.com/118      )

  

-- [백준 1012번 C++] 유기농 배추

위와 행렬로 입력을 받지만, 여기서는 정사각형 모양의 지도여서 양배추 문제보다는 난이도가 낮았던 것 같다. 

단지의 개수를 구하고, 단지에 속한 집의 개수까지 저장해서 정렬하여 출력을 해야했던 문제였다. 

 

처음엔 유기농 배추처럼 코드를 다음과 같이 초안 코드를 짰다. 하지만 출력이 나오지 않았는데 알고보니 입력을 공백 없이 다음과 같이 받아서 string으로 한번에 받아오고 나눠주는 식으로 행렬을 저장해야했던 것이다. 

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

 

문제의 코드

#include <iostream>
using namespace std;

int map[26][26]={0,};
int visited[26][26] = {0,};
int xpos[4] = {-1, 1, 0, 0 }; 
int ypos[4] = {0, 0, 1, -1};
int n;
 
void dfs(int x, int y){
    visited[x][y] = 1;
    cout <<  "x, y = " << x << " " << y << "\n";
    
    for(int i=0; i<4; i++){
        int nxpos = x + xpos[i];
        int nypos = y + ypos[i];
        
        if( nxpos < 0 || nxpos >= n || nypos < 0 || nypos >= n) continue;
        if(visited[nxpos][nypos]==0 && map[nxpos][nypos]==1) dfs(nxpos, nypos);
    }
    
}

int main()
{
  
   cin >> n;
   
   for(int i=1; i<=n; i++){
       for(int j=1; j<=n; j++){
           cin >> map[i][j];
       }
   }

    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(map[i][j]==1 && visited[i][j]==0) dfs(i, j);
        }
    }
    
    return 0;
}

 

문제점2 : 변수를 count를 둬서 ambiguous error가 뜸

#include <algorithm> 을 하면 count라는 function이 있어서 count라는 변수를 쓸 때 생기는 에러이다. 

count를 cnt로 바꾸었더니 해결 됨.

 

https://stackoverflow.com/questions/11271889/global-variable-count-ambiguous

Global variable "count" ambiguous

---

문제점3 : 상하좌우 이동의 범위를 잘못 줌

    for(int i=0; i<4; i++){
        int nxpos = x + xpos[i];
        int nypos = y + ypos[i];
        
        if( nxpos < 1 || nxpos > n || nypos < 1 || nypos > n) continue;
        if(visited[nxpos][nypos]==0 && map[nxpos][nypos]==1) dfs(nxpos, nypos);
    }

이번에는 행렬의 인덱스를 0부터 n-1로 준 게 아니라, 1부터 n으로 설정했다.

따라서 새로운 x좌표인 nxpos와 새로운 y좌표인 nypos의 범위도 위와 같이 설정해줘야 했다. 

이를 해결하니 count가 잘되어 출력이 됨! 

 

문자열에서 정수로 변환 - 48을 빼기

48을 빼기 

이젠 정말 외우기

대문자에서 소문자 변환하려면 32를 더하기  

16의 배수로 외우면 되겠다!

 

단지의 개수 세기 

이제 총 몇 개의 단지가 있고, 그 단지에 집이 몇 개가 있는지 저장해야한다. 

배열은 크기가 정해져 있으니 적합하지 않고 벡터를 이용하는 게 좋을 것 같다고 판단했다. 

총 몇 개의 단지는 벡터의 크기로 출력하면 되고, 한 단지에 있는 집의 개수만 벡터에 넣어주면 된다. 

 

---

최종 코드

와 푸는데 4시간 걸렸다

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

int map[26][26]={0,};
int visited[26][26] = {0,};
int xpos[4] = {-1, 1, 0, 0 }; 
int ypos[4] = {0, 0, 1, -1};
int n;

//집의 개수를 저장할  벡터, 집의 개수를 count할 변수 count  
vector<int> v;
int cnt;

void dfs(int x, int y){
    cnt++;
    visited[x][y] = 1;
    
    for(int i=0; i<4; i++){
        int nxpos = x + xpos[i];
        int nypos = y + ypos[i];
        
        if( nxpos < 1 || nxpos > n || nypos < 1 || nypos > n) continue;
        if(visited[nxpos][nypos]==0 && map[nxpos][nypos]==1) dfs(nxpos, nypos);
    }
    
}

int main()
{
  
   cin >> n;
  //string으로 입력 받고 나눠서 행렬에 저장하기
    string str;
   for(int i=1; i<=n; i++){
       cin >> str;
       for(int j=0; j<n; j++){
           //문자열에서 정수로 변환하려면 48을 빼면 됨
           map[i][j+1] = str[j] - 48 ;
       }
   }
    

    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(map[i][j]==1 && visited[i][j]==0) {
                cnt = 0;
                dfs(i, j);
                v.push_back(cnt);
            }
        }
    }
    
    cout << v.size() << endl;
    sort(v.begin(), v.end());
    for(int i = 0; i < v.size(); i++) 
        cout << v[i] <<endl;
    
    return 0;
}