[백준2667] 단지번호붙이기

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

2667번: 단지번호붙이기

 

문제설명

지도에서  현재 자신이 있는 곳(집)에서 집이 상하좌우 중 어느 한 곳이라도 연속이 되면 단지로 판단하고, 단지의 개수, 단지에 속한 집의 개수를 세아려서 오름차순으로 정렬하여 한줄에 하나씩 출력한다. 

문제 해결 방법

BFS로 문제를 풀었다. 

코드 구현

import java.io.InputStreamReader;
import java.awt.Point;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
	public static int N;
	public static int cnt = 0;
	public static int totalCnt = 0;
	public static int[][] graph;
	public static int[] dx = {1, -1, 0, 0};
	public static int[] dy = {0, 0, 1, -1};
	public static String A="";
	public static int[] sortt;

	public static ArrayList<Integer> list = new ArrayList<>();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		N = Integer.parseInt(br.readLine());
		
		graph = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			Arrays.fill(graph[i], 0);
		}
		
		for(int i = 0; i < N; i++) {
			String str = br.readLine();
			for(int j = 0; j < N; j++) {
				graph[i][j] = Character.getNumericValue(str.charAt(j));
			}
		}
		for(int i = 0; i<N; i++) {
			for(int j = 0; j<N; j++) {
				BFS(i, j);
				cnt=0;
			}
		}
		
		System.out.println(totalCnt);
		
		Collections.sort(list);
			
		for(Object a : list) {
			System.out.println(a);
		}
		
	}
	
	public static void BFS(int start1, int start2) {
		Queue<Point> q = new LinkedList<Point>();
		q.add(new Point(start1, start2));
		cnt = 0;
		
		while(!q.isEmpty()) {
			Point p = q.poll();
			
			if(graph[p.x][p.y]==1) {
				graph[p.x][p.y] = 9;
				cnt+=1;
			}
			
			for(int i = 0; i < 4; i++) {
				int x = p.x + dx[i];
				int y = p.y + dy[i];
				
				
				if(x < 0 || y < 0 || x >= N || y >= N) {
					continue;
				}
				
				if(graph[p.x][p.y]==0) {
					if(graph[x][y]==1) {
					}
				}
				
				
				if(graph[x][y]==1 && graph[p.x][p.y]!=0) {
					q.add(new Point(x, y));
					graph[x][y] = 9;
					cnt += 1;
				}
			}
			
		}
		
		if (cnt!=0) {
			totalCnt+=1;=
			list.add(cnt);
		}
	}
}

시간/공간 복잡도

O(N^2)

최적화 및 개선

따로 하지않음

어려웠던 점

처음에 ArrayList 사용할 생각을 못했다.
문자열에 각 단지의 개수를 추가한 후, 출력할 때 문자 하나하나 CharAt()으로 잘라서 출력했더니,
단지의 수가 9가 넘는 것들(두자리 수)의 값을 출력해야할 상황에는 다 런타임 에러가 났다. 

ArrayList가 답이다,, 이것을 이용하면 Collections를 이용해서  sort도 굉장히 편하게 할 수 있다.. 

버티지 말자~ 모르면 찾아보자