[백준 2667] 알고리즘 82일차 : 단지번호붙이기

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

C++ DFS&BFS

이차원 배열을 그래프로 표현해서 DFS&BFS로 푸는 문제



접근방법

처음엔 이걸 인접 그래프로 만들어서 풀어야 하나 했지만 그냥 지도랑 방문여부만 배열로 만들어서 풀어도 되는 문제였다.

지도를 한칸씩 돌면서 집이 있고 & 방문하지 않은 집이 나오면 DFS에 들어간다.

DFS안에서는 우선 현위치를 방문하고/cnt를 1증가하고/상하좌우를 돌면서 집이 있으면 재귀로 DFS를 들어간다/ << 방문하지 않은 연결된 집이 없을 때까지 이거 반복

DFS끝나면 cnt를 cnts(단지별 집개수 저장 벡터)에 푸시한다/cnt를 0으로 초기화

그리고 마지막에 지도를 다 돌고 난 후엔 cnts의 사이즈 (단지 수) 와 단지별 집 개수를 출력하면 끝

 

오답노트

지도랑 방문여부 배열을 최대 25*25로 설정했는데 틀렸습니다 떠서

26*26으로 설정했더니 통과됐다.(이거 왜 돼 모먼트)

위치가 우측변, 아래쪽변에 있을때 상하좌우를 확인할때 범위를 하나씩 벗어나서 그렇게 되는 것 같다.

다른분들은 잘 되긴 하던데,,

(풀이시간 대략 45분..?)

 

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
bool map[26][26];
bool visit[26][26];
int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};
vector<int> cnts;
int cnt = 0;
void dfs(int r, int c){
    cnt++;
    visit[r][c] = true;
    for(int i = 0 ; i < 4 ; i++){
        int nr = r+dr[i];
        int nc = c+dc[i];
        if(!visit[nr][nc] && map[nr][nc]){
            dfs(nr,nc);
        }
    }
}
int main(){
    cin >> n;
    char c;
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < n ; j++){
            cin >> c;
            map[i][j] = c-'0';
        }
    }

    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < n ; j++){
            if(map[i][j] && !visit[i][j]){
                dfs(i,j);
                cnts.push_back(cnt);
                cnt = 0;
            }
        }
    }
    sort(cnts.begin(),cnts.end());
    cout << cnts.size() << "\n";
    for(int i = 0 ; i < cnts.size() ; i++){
        cout << cnts[i] << "\n";
    }
    return 0;
}