Hyemi Lee

Hyemi Lee

주니어 개발자의 삽질과 기록

Algorithm, boj, 2267(단지번호붙이기)

  • BFS

  • (0,0) 부터 (size,size) 까지 돌면서 방문하지 않은 집을 찾는다.
  • 집을 찾으면, 단지+1을 해주고 해당 단지의 집들을 BFS로 방문하며 집의 숫자를 구한다.
  • 틀렸다는데...왜 틀렸을까? 헝헝 ᅲᅲ
package org.baekjoon;
import java.io.*;
import java.util.*;
public class test2667 {
	static int[][] arr;
	static int size;
	static boolean[][] visited;
	// 점의 방향
	static int[] Dx = {-1, 1, 0, 0};
	static int[] Dy = {0, 0, -1, 1};
 	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input;
		size = Integer.parseInt(br.readLine());
		arr = new int[size][size];
		for(int i=0; i<size; i++) {
			input = br.readLine();
			for(int j=0; j<size; j++) {
				arr[i][j] = input.charAt(j) - '0';
			}
		}
		ArrayList<Integer> houseCount = new ArrayList<Integer>();
		visited = new boolean[size][size];
		int group = 0;
		// 전체를 돌며 1인 점을 찾는다
		for (int i=0; i<size; i++) {
			for (int j=0; j<size; j++) {
				// 이미 방문한 점이라면 패스
				if (visited[i][j] == true) continue;
				// 방문하지 않은 집이라면 새로운 단지+1 , 단지내 집의 수 구하기
				if(arr[i][j] == 1) {
					// 단지 +1
					group++;
					houseCount.add(BFS(i,j));
				}
			}
		}
		// 결과 출력
		System.out.println(group);
		Collections.sort(houseCount);
		for(int e:houseCount)
			System.out.println(e);
	}
	static int BFS(int x, int y) {
		int houseCount = 0;
		Queue<dot> qu = new LinkedList<dot>();
		qu.offer(new dot (x, y));
		while (!qu.isEmpty()) {
			// 방문할 큐 맨앞 점을 하나 뽑는다.
			dot Cd = qu.poll();
			int Cx = Cd.x;
			int Cy = Cd.y;
			// 뽑힌 점의 상하좌우를 확인한다.
			for (int i=0; i<4 ;i++) {
				int Nx = Cx + Dx[i];
				int Ny = Cy + Dy[i];
				// 상하좌우의 점이 범위 내에 있는지 확인한다.
				if (0 <= Nx && Nx < size && 0 <= Ny && Ny < size) {
					// 집이 있고 방문하지 않았으면
					if (arr[Nx][Ny] == 1 && visited[Nx][Ny] == false) {
						// 방문한다
						visited[Nx][Ny] = true;
						qu.offer(new dot(Nx,Ny));
						// 집의 숫자를 세어준다.
						houseCount++;
					}
				}
			}
		}
		return houseCount;
	}
}
class dot{
	int x;
	int y;
	dot(int x, int y){
		this.x = x;
		this.y = y;
	}
}

Reference

문제로 가기 문제 풀이 참고

Share on

Twitter Facebook LinkedIn

You may also enjoy

Redis Stream

2021年04月28日

Stream Stream은 로그 데이터를 처리하게위해 5.0에서 새로 도입된 데이터 타입입니다. 대량의 데이터가 연속적으로 발생할때 처리하기 위해 등장했습니다. 기존 데이터를 수정하지 않고 오직 추가로 발생합니다. 이런 종류의 데이터를 stream or log데이터...

Study, Object, chapter2&3 presentation

2021年04月20日

chapter03. 역할, 책임, 협력 객체지향 설계란, 올바른 객체에게 올바른 책임을 할당하면서 낮은 결합도와 높은 응집도를 가진 구조를 창조하는 활동이다.

Spring, chatting 프로그램 만들기, Reactive란?

2020年06月16日

Reactive 막힘없이 흘러다니는 data(event)를 통해 사용자에게 자연스러운 응답을 주고 규모 탄력적으로 리소스를 사용하며 실패에 있어서 유연하게 대처한다 모든 지점에서 블럭 되지 않게 하자 oop와 같은 패러다임 모든 것을 비동기적인 data의 strea...