ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 2667.단지번호붙이기
    알고리즘/백준 BAEK JOON 2020. 5. 21. 23:40

    이번에 풀어볼 문제는 단지번호붙이기이다.

     

    2667번: 단지번호붙이기

    <그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. �

    www.acmicpc.net

    생각보다 이상한곳에 막혀서 시간낭비를 했다. 시간은 1시간 30분정도 걸렸고 목표한 시간보다 30분이나 초과되었다.

    사실 30분컷 낼 수 있었는데 이걸 코드하나를 잘못집어넣어서 하루종일 걸렸다.. 후... 

    DFS를 이용해서 풀었고 이 문제의 포인트는 Stack를 이용하되 Stack에 자신이 이동한 부분의 좌표를 넣어주는 것이다.

    그래야지 DFS로 쭈욱 탐색하다가 막혔을 때 다시 돌아가서 탐색하지 않은 방향으로 탐색을 진행할 것이다.

     

    < Code 설명 >

    #pragma warning(disable:4996)
    #include <iostream>
    #include <queue>
    #include <stack>
    #include <algorithm>
    
    #define MAX 26
    
    using namespace std;
    
    bool check[MAX][MAX];
    int map[MAX][MAX];
    int n;
    int dx[4] = { -1, 1, 0, 0 }; //이동 x좌표
    int dy[4] = { 0, 0, -1, 1 }; //이동 y좌표
    
    stack <pair<int, int>>ss;
    
    int dfs(){
    	int x = ss.top().first; // stack의 x좌표 사용
    	int y = ss.top().second;// stack의 y좌표 사용
    	check[x][y] = true; 첫 시작구간은 들렸으므로 true로 체크
    	int cnt = 1; // 몇개의 단지가 존재하는지 세는 변수
    	while (!ss.empty()){ // stack이 빌 때까지
    		for (int i = 0; i < 4; i++){ //좌표 이동 후 탐색을 위한 for문
    			int ax = x+dx[i]; // 선택한 좌표에서 x좌표이동 탐색
    			int ay = y+dy[i]; // 선택한 좌표에서 y좌표이동 탐색
    
    			if (ax < 0 || ay <0 || ax>n || ay>n) //좌표가 map 벗어나지면
    				continue; // 넘어간다.
    
    			if (!check[ax][ay] && map[ax][ay] == 1){ //미탐색 && 단지존재
    				check[ax][ay] = true; // 탐색으로 체크
    				ss.push(make_pair(ax, ay)); // 탐색한 부분 stack에 push
    				x = ss.top().first; //해당좌표로 이동하기위함
    				y = ss.top().second;//해당좌표로 이동하기위함
    				i = -1; // 이동한채로 다시 탐색하기위함
    				cnt++;  // 단지 ++
    			}
    		}
    		if (!ss.empty()){ //스택이 안비었다면 스택의 top으로 할 수있는 탐색 끝났으므로
    			ss.pop(); //탐색끝난 좌표 pop
    			if (!ss.empty()){ //그래도 남았다면 이전의 스택에서 미탐색 좌표가 있을지모르니
    				x = ss.top().first; // 해당 좌표로 다시돌아가 4방향탐색
    				y = ss.top().second;
    			}
    		}
    	}
    	return cnt; // 단지 숫자를 리턴해줌
    }
    
    int main() {
    	cin >> n;
    	int cnt = 0;
    	for (int i = 0; i < n; i++){
    		for (int j = 0; j < n; j++){
    			scanf("%1d", &map[i][j]);
    		}
    	}
    	vector<int>v;
    	for (int i = 0; i < n; i++){
    		for (int j = 0; j < n; j++){
    			if (map[i][j] == 1 && !check[i][j]){ // 미탐색 && 단지존재 
    				ss.push(make_pair(i, j)); // 스택에 해당 좌표 넣음
    				v.push_back(dfs()); // dfs 진행 후 return값 vector에 저장
    			}
    		}
    	}
    	sort(v.begin(), v.end()); // 오름차순 정렬
    	cout << v.size() << "\n"; // 백터 크기 출력
    	for (int i = 0; i < v.size(); i++){ // 단지 숫자들 하나씩 출력
    		cout << v[i] << "\n";
    	}
    
    
    	return 0;
    }

     

    '알고리즘 > 백준 BAEK JOON' 카테고리의 다른 글

    7576.토마토  (0) 2020.05.25
    14502.연구소  (0) 2020.05.25
    2667.단지번호붙이기  (0) 2020.05.21
    15649 ~ 15652.N과 M(1~4)  (0) 2020.05.20
    1541.잃어버린 괄호  (2) 2020.05.18
    2529.부등호  (0) 2020.05.18

    댓글 0

Designed by Tistory.