2667_단지번호붙이기 (JAVA) (C++)

2667번: 단지번호붙이기

 

[C++] - ① BFS

#include <iostream>
#include <algorithm> //sort
#include <queue>
#include <vector>
using namespace std;

int n;
int map[25][25];
bool visited[25][25] = {false};
vector<int> danji;

struct XY{
    int x; int y;
};
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};

void bfs(XY xy){
    int cnt = 1;

    queue<XY> q;
    q.push({xy.x, xy.y});

    while(!q.empty()){
        XY cur = {q.front().x, q.front().y};
        q.pop();

        for(int i=0; i<4; i++){
            XY next = {cur.x+dx[i], cur.y+dy[i]};
            
            if(next.x>=0&&next.x<n && next.y>=0&&next.y<n){
                if(!visited[next.x][next.y] && map[next.x][next.y]==1){
                    visited[next.x][next.y] = true;
                    q.push({next.x, next.y});
                    cnt++;
                }
            }
        }
    } 
    danji.push_back(cnt); 
}

int main(){
    cin >> n;
    for(int i=0; i<n; i++){
        string str;
        cin >> str;
        for(int j=0; j<str.size(); j++){
            map[i][j] = str[j]-'0';
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(!visited[i][j] && map[i][j]==1){
                visited[i][j] = true;
                XY cur = {i,j};
                bfs(cur);
            }
        }
    }

    sort(danji.begin(), danji.end());

    cout << danji.size() << endl;
    for(int i=0; i<danji.size(); i++){
        cout << danji[i] << endl;
    }

    return 0;
}

 

 

 

[C++] - ② DFS

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

int n;
int map[25][25];
bool visited[25][25] = {false};
vector<int> danji;
int cnt = 0;

struct XY{
    int x; int y;
};
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};

void dfs(XY cur){
    for(int i=0; i<4; i++){
        XY next = {cur.x+dx[i], cur.y+dy[i]};
        
        if(next.x>=0&&next.x<n && next.y>=0&&next.y<n){
            if(!visited[next.x][next.y] && map[next.x][next.y]==1){
                visited[next.x][next.y] = true;
                cnt++;
                dfs(next);
            }
        }
    }
}

int main(){
    cin >> n;
    for(int i=0; i<n; i++){
        string str;
        cin >> str;
        for(int j=0; j<str.size(); j++){
            map[i][j] = str[j]-'0';
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(!visited[i][j] && map[i][j]==1){
                visited[i][j] = true;
                XY cur = {i,j};
                
                cnt = 1;
                dfs(cur);
                danji.push_back(cnt);
            }
        }
    }

    sort(danji.begin(), danji.end());

    cout << danji.size() << endl;
    for(int i=0; i<danji.size(); i++){
        cout << danji[i] << endl;
    }

    return 0;
}

 

 

 

 

[JAVA] - BFS

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	static int N;
	static int dx[]={-1,1,0,0};
	static int dy[]={0,0,-1,1};
	static int[][] visited;
	static int[][] map;
	static List<Integer> ansList = new ArrayList<Integer>();
	
	static class XY{
		int x, y;
		public XY(int x, int y){
			this.x = x; this.y = y;
		}
	}
	
	public static void main (String[] args) 
	{
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		map = new int[N][N];
		visited = new int[N][N];
		
		for(int i=0; i<N; i++){
			String temp = sc.next();
			for(int j=0; j<N; j++){
				map[i][j] = temp.charAt(j)-'0';
			}
		}
		
		for(int i=0; i<N; i++){
			for(int j=0; j<N; j++){
				if(map[i][j]==1 && visited[i][j]==0){
					BFS(i, j);
				}
			}
		}
		
		System.out.println(ansList.size());
		Collections.sort(ansList);
		for(int i=0; i<ansList.size(); i++){
			System.out.println(ansList.get(i));
		}
	}
	
	static void BFS(int a, int b){
		Queue<XY> q = new LinkedList<XY>();
		q.offer(new XY(a,b));
		visited[a][b]=1;
		
		int ans=1;
		while(!q.isEmpty()){
			int x = q.peek().x;
			int y = q.peek().y;
			q.poll();
			
			for(int i=0; i<4; i++){
				int xx = x+dx[i];
				int yy = y+dy[i];
				
				if(xx>=0&&xx<N && yy>=0&&yy<N){
					if(map[xx][yy]==1 && visited[xx][yy]==0){
						map[xx][yy] = map[x][y]+1;
						q.offer(new XY(xx,yy));
						visited[xx][yy]=1;
						ans++;
					}
				}
			}
		}
		ansList.add(ans);
	}
	
}

 

 

1. 이어져있는거를 판단하는건 큐로! 그런데 이어져있는게 여러개니까 BFS()함수로 빼서 구현했다.

 

2. map에서 1인 곳을 만나면 BFS()함수로, 큐에 넣고 1로 이어져있는게 없을때까지 while문을 돌린다.

   1로 이어져있으면 총 개수를 세기 위해서- map[xx][yy]=map[x][y]+1; 로 +1해준다. (개수 세기 용도!)

 

3. 동적 배열인 List에 위에서 센 총 개수를 넣어준다.

 

4. Collections.sort(List)로 오름차순 정렬하고 출력!