-
[백준] 2667 단지번호붙이기 - Java알고리즘 문제 풀이 2024. 5. 27. 14:27
문제 - 단지번호붙이기
https://www.acmicpc.net/problem/2667
접근 방법
이 문제도 그래프 탐색 문제이다
bfs, dfs 둘다 사용해서 풀 수 있는 문제이다
작성자는 bfs로 풀었다
각각의 영역이 몇개있는지 수를 세고 해당 영역의 요소가 몇개가 있는지 수를 세었다
흔한 그래프 탐색 문제이다
코드 작성(bfs)
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.List; import java.util.Queue; public class Main { static int N; public static void main(String[] args) throws IOException { try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) { N = Integer.parseInt(br.readLine()); int[][] map = new int[N][N]; boolean[][] visited = new boolean[N][N]; int count = 0; for (int i = 0; i < N; i++) { map[i] = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray(); } List<Integer> result = new ArrayList<>(); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (!visited[i][j] && map[i][j] == 1) { count++; result.add(bfs(i, j, map, visited)); } } } System.out.println(count); result.sort(Integer::compareTo); for (int data : result) { System.out.println(data); } } } public static int bfs(int x, int y, int[][] map, boolean[][] visited) { int[] dx = {-1, 1, 0, 0}; int[] dy = {0, 0, -1, 1}; Queue<int[]> queue = new LinkedList<>(); queue.add(new int[] {x, y}); visited[x][y] = true; int count = 1; while (!queue.isEmpty()) { int[] poll = queue.poll(); int pollX = poll[0]; int pollY = poll[1]; for (int i = 0; i < 4; i++) { int ix = pollX + dx[i]; int iy = pollY + dy[i]; if (ix >= 0 && ix < N && iy >= 0 && iy < N) { if (map[ix][iy] == 1 && !visited[ix][iy]) { queue.add(new int[] {ix, iy}); visited[ix][iy] = true; count++; } } } } return count; } }
'알고리즘 문제 풀이' 카테고리의 다른 글
[프로그래머스] 네트워크 - Java (0) 2024.05.30 [백준] 15670 N과 M(2) - Java (0) 2024.05.29 [백준] 2839 설탕 배달 - Java (0) 2024.05.25 [백준] 2606 바이러스 - Java (0) 2024.05.23 [백준] 5568 카드 놓기 - Java (0) 2024.05.22