[백준2667] 단지번호 붙히기 (C++, Java)

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

 

풀이방법

• BFS로 순회하면서 visit처리해준다.
• 단지가 끝나면 새로운 단지를 찾는다. 찾으면 총 단지수를 ++ 해준다
• 새로운 단지 BFS하며 q에서 pop할때 마다 각 단지의 수 해주어 각 단지의 갯수를 구한다.
• Java에서 Vector 대신 List를 써주며 sort 법이 조금 다르다.

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int ar[26][26];
int vi[26][26];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
int n;
vector<int> v;
vector<int> ans;
int ct = 0; int ct2 = 0;

void input() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) scanf("%1d", &ar[i][j]);
	}
}

void bfs(int i, int j) {
	ct = 0;
	ct2++;
	queue<pair<int, int>> q;
	q.push({ i, j });
	vi[i][j] = 1;
	while (!q.empty()) 
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		ct++;

		for (int w = 0; w < 4; w++) {
			int nx = x + dx[w];
			int ny = y + dy[w];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n)
				continue;
			if (ar[nx][ny] != 0 && vi[nx][ny] == 0) 
			{
				vi[nx][ny] = 1;
				q.push({ nx, ny });
			}
		}
	}

	v.push_back(ct);
}

void solve() {
	for (int i = 0; i < n; i++) 
	{
		for (int j = 0; j < n; j++) 
		{
			if (ar[i][j] != 0 && vi[i][j] == 0) 
				bfs(i, j);
		}
	}
	ans.push_back(ct2);
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++) ans.push_back(v[i]);
}

int main() {
	input();
	solve();
	for (int i = 0; i < ans.size(); i++) cout << ans[i] << endl;
	return 0;
}

 

Java

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*; 

class Node
{
	int x;
	int y;
	ArrayList<String> list;
	Node(int x, int y)
	{
		this.x = x;
		this.y = y;
		this.list =new ArrayList<String>();
	}
}

public class 백준2667_단지번호붙히기_DFSBFS1 
{
	ArrayList<ArrayList<String>> list4 = new ArrayList<ArrayList<String>>();
	static int house[][];
	static boolean[][] visited;
	static int N;
	static int dir_x[]= {-1,1,0,0};
	static int dir_y[]= {0,0,-1,1};
	
	static ArrayList<Integer> listall= new ArrayList<Integer>();
	static ArrayList<Integer> list= new ArrayList<Integer>();
	//static Stack<Node> stck= new Stack<Node> ();
	static int count=0;
	static int ct =0;
	static int ct2 =0;
	
	public static void bfs(int i, int j )
	{
		ct =0;
		ct2++;
		Queue <Node> q = new LinkedList<Node> ();
		q.add(new Node(i,j));
		while(!q.isEmpty())
		{
			Node p = q.poll(); 
			int x = p.x;
			int y = p.y;
			visited[x][y] =true;
			ct++;
			for(int w= 0 ; w <4 ; w++)
			{
				int nx = x + dir_x[w];
				int ny = y + dir_y[w];
				
				if (nx <0 || nx >=N || ny < 0 || ny >=N)
					continue;
				if(visited[nx][ny])
					continue;
				if(house[nx][ny] !=0)
				{
					q.add(new Node(nx,ny));
					visited[nx][ny] =true;	
				}
				
			}
					
		}
		
		list.add(ct);
	}
	
	
	public static void solve()
	{
		for (int i = 0; i < N; i++) 
		{
			for (int j = 0; j < N; j++) 
			{
				if (house[i][j] != 0 && visited[i][j] == false) 
					bfs(i, j);
			}
		}
		listall.add(ct2);
		Collections.sort(list);
		for(int i = 0 ; i<list.size();i++)
		{
			listall.add(list.get(i));
		}
	}
	
	public static void main(String[] args) throws IOException 
	{
		BufferedReader br= new BufferedReader (new InputStreamReader(System.in));
		String input= br.readLine();
		N = Integer.parseInt(input);
		house = new int [N][N];
		visited = new boolean [N][N];
		//Arrays.fill(visited, false);
		for(int i = 0 ; i < N; i++)
		{
			input = br.readLine();
			for(int j =0 ; j < N ; j++)
			{
				int tempNum = input.charAt(j);
				house[i][j] = input.charAt(j) -'0'; 
			}
		}
		solve();
		
		//System.out.println(list.size());
		for (int i=0; i<listall.size(); i++)
		{
			System.out.println(listall.get(i));
		}
		// TODO Auto-generated method stub

	}

}