[백준알고리즘] 2667번 : 단지번호붙이기 #스터디 1주차

문제는 아래 사이트에 들어가면 확인 할 수 있다.

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

2667번: 단지번호붙이기

먼저 선언한 변수 및 배열들이다. 

N : 전체 배열 크기 N*N을 위한 변수

map[max][max] : 지도 용 배열, 집의 여부를 표시할 것이다.

visit[max][max] : 방문 체크용 배열, 같은 단지를 순회하지 못하게 체크해주기 위함

countN : 단지 내의 몇개의 집이 있는지 체크하기 위한 변수

vector<int> v : 단지 순회 완료후 단지의 countN개수 보관

int pos[4][2] : 상하좌우 좌표를 위한 변수

 

 

예제 입력에서는 지도의 크기N과, N줄 동안 N개의 자료를 입력한다. 

띄어쓰기 구분자가 없으므로,  각 문자를 %1dfh 받아서 입력해주었다. 

 

그 다음, map[0][0]부터 출발한다. 1인 값을 확인하고, 방문 여부를 체크해주어야 한다. 

dfs를 통해 한번 순회한 단지인데 다시 순회하면 안되기 때문이다. 

조건이 성립하면 count를 0으로 초기화해주는데 이는 단지 내의 집이 몇개인지 세어주기 위함이다.

또 dfs에서 재귀함수를 통해 count를 세어주기 때문에, dfs함수 호출 이후에 vector v에 현재 순회한 단지내 집의 수를 push_back 해준다. 

 

dfs순회를 위한 함수이다. 

row와 column을 매개변수로 입력받았고, 현재 찾은 집 위치 map[r][c]에 들어올 때마다 count 를 증가해주었다.

방문여부 역시 생성했던 배열 visit로 true로 만들어준다.

현재 위치 r,c의 상하좌우를 nr, nc 라는 변수에 할당해준다. 4번 반복함으로서 상하좌우를 한번씩 확인한다. 

 

1) 배열의 내부인지 확인하는 조건 : nr,nc가 0보다 큰 값인가 , 전체 크기인 N보다 작은값인가 확인한다.

2) 집이 존재하는 지 확인 : map[nr][nc] 값이 1인지 확인한다.

3) 방문 여부 확인 : visit[nr][nc] 값이 false인지 확인한다. 

 

위의 세가지 조건에 만족할 때 nr, nc로 dfs를 재귀호출한다.  더이상 호출할 집이 없을 때 이 반복문은 종료될 것이며, 그 때 count값이 최종 현재 단지 내의 집 개수이다. 

 

모든 단지를 다 순회한 후에 vector의 size는 단지의 개수가 된다. 

sort함수를 통해 vector를 정렬해주고, 

벡터의 사이즈만큼 반복해서 각 단지에 집이 몇개씩 있는지 출력해주면 끝!

 

 

<전체 코드>

 

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

#include <iostream> #include <algorithm> #include<vector> #include <cstring>   using namespace std;   #define MAX  25 int N; //size of map int map[MAX][MAX]; int visit[MAX][MAX];   int countN; vector<int> v;   int pos[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; //상하좌우   void dfs(int r, int c) { //r= row, c = column     countN++;     visit[r][c] = true;     for (int i = 0; i < 4; i++) {         int nr = r + pos[i][0];         int nc = c + pos[i][1];           //배열 내부확인, 값이 1인가, 방문을 하지 않았는가.         if (nr >= 0 && nr < N && nc >= 0 && nc < N && map[nr][nc]== 1 && !visit[nr][nc] ) {             dfs(nr,nc);         }         } } int main() {     string s;     cin >> N;       for (int i = 0; i < N; i++) {         for (int k = 0; k < N; k++) {             scanf("%1d", &map[i][k]);         }     }       for (int i = 0; i < N; i++) {         for (int k = 0; k < N; k++) {             if (map[i][k] == 1 && !visit[i][k]) {                 countN = 0;                 dfs(i,k);                 v.push_back(countN);             }         }     }       sort(v.begin(), v.end());     cout << v.size() << '\n';     for (int i = 0; i < v.size(); i++) {         cout << v[i] << '\n';     }       return 0; } Colored by Color Scripter

cs