[Baekjoon] 백준 2667 단지번호붙이기 (S1^ / BFS) - Java

링크

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

2667번: 단지번호붙이기

 

 

 

문제 해석

집이 모여있는 단지 개수를 구하기

각각 하나의 단지가 가진 집의 개수를 구하고 이를 오름차순으로 출력 

 

 

 

코드

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

public class Main2 {
	static int[][] map; // 맵 정보 저장 변수
	static int answer; // 총 단지 개수
	static ArrayList<Integer> count = new ArrayList<>(); // 단지 크기

	static int[] dx = { 0, -1, 0, 1 }; // 4방 탐색
	static int[] dy = { -1, 0, 1, 0 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());

		map = new int[N][N];

		// input
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			String[] s = st.nextToken().split("");
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(s[j]);
			}
		}

		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				// 탐색할 위치를 찾으면
				if (map[i][j] == 1) {
					bfs(i, j);
					answer++;
				}
			}
		}

		System.out.println(answer);
		Collections.sort(count);
		for (int i = 0; i < count.size(); i++) {
			System.out.println(count.get(i));
		}
	}

	static class Point { // q에 정보를 저장할 노드 객체
		int x;
		int y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	private static void bfs(int i, int j) {
		Queue<Point> q = new LinkedList<>(); // 노드 정보를 저장할 Queue

		q.offer(new Point(i, j));

		int counter = 1;

		while (!q.isEmpty()) { // q가 빌때까지 반복
			Point p = q.poll();
			map[p.x][p.y] = 0;

			for (int k = 0; k < dx.length; k++) {
				int cx = p.x + dx[k];
				int cy = p.y + dy[k];

				if (cx >= 0 && cx < map.length && cy >= 0 && cy < map[0].length 
				&& map[cx][cy] == 1) { // 조건에 맞으면
					map[cx][cy] = 0;
					q.offer(new Point(cx, cy)); // q에 데이터 추가
					counter++;
				}
			}
		}
		count.add(counter);
	}
}

 

 

 

코드 해석

BFS의 가장 기본적인 문제입니다.

 

각 단지에 위치한 아파트 개수를 count해주는 단순한 기능 구현을 요구합니다.

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

source : https://github.com/ssh5212/conding-test-practice