일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- LiveTemplate
- github
- Intellij
- 논리학
- Leetcode
- 서버중단
- github cli
- string
- 데이터센터
- 통신대란
- 코딩테스트
- 큐
- Java
- OVH
- 서버오류
- linux
- 자료형
- elasticbeanstalk
- AWS
- Queue
- thymeleaf
- 자동완성
- dfs
- 백준
- char[]
- 명제
- JAVA기초
- 코테
- 알고리즘
- springboot
- Today
- Total
Midnight Coder's Lounge
[백준][JAVA] 2667 - 단지번호붙이기 (11612KB, 64ms, Java 8) 본문
실버1 티어 DFS 문제인 단지번호붙이기 문제 풀이입니다.
제법 많은 분들께서 제 문제 풀이를 조회해 주셔서, 블로그에 직접 문제 해설을 올리기로 마음먹었습니다.
* 선수지식 : DFS, PriorityQueue
문제 링크
https://www.acmicpc.net/problem/2667
개요
"이차원 평면 위에 1로 표현된 '집'들을 상하좌우로 연결한 묶음을 '단지'라고 하겠습니다.
첫째 줄에 총 단지 수가 몇 개인지 출력해 주세요.
그 후 단지별로 들어 있는 집의 수를 오름차순 정렬해서 한 줄씩 출력해 주세요."
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
public class Main {
static int N;
static boolean[][] map;
static int[] dR = {0, 0, -1, 1};
static int[] dC = {-1, 1, 0, 0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new boolean[N][N];
for (int i = 0; i < N; i++) {
String input = br.readLine();
for (int j = 0; j < N; j++) {
map[i][j] = (input.charAt(j) == '1');
}
}
int answer = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if(map[r][c]){
answer++;
pq.offer(dfs(r, c));
}
}
}
StringBuilder sb = new StringBuilder();
sb.append(residence).append('\n');
while(!pq.isEmpty()){
sb.append(pq.poll()).append('\n');
}
System.out.print(sb);
}
static int dfs(int r, int c){
map[r][c] = false;
int nr, nc;
int houses = 1;
for (int dir = 0; dir < 4; dir++) {
nr = r + dR[dir];
nc = c + dC[dir];
if(isInBound(nr, nc)){
houses += dfs(nr, nc);
}
}
return houses;
}
static boolean isInBound(int r, int c){
return r >= 0 && c >= 0 && r < N && c < N && map[r][c];
}
}
해설
📌이차원 배열 초기화 : boolean[][] 타입 사용
표현하려는 값이 0과 1밖에 없어서 int[][] 보다 메모리를 적게 사용하는 boolean[][] 을 사용해도 충분합니다.
입력 1로 주어지는 '집'은 true 로, 입력 0으로 주어지는 빈 공간은 false 로 치환합니다.
참고로 이 이차원 배열은 집의 위치를 나타낼 뿐만 아니라 방문 체크 역할까지 겸할 예정입니다.
map = new boolean[N][N];
for (int i = 0; i < N; i++) {
String input = br.readLine();
for (int j = 0; j < N; j++) {
// 입력을 받아서 값이 1이면 true, 0이면 false를 대입합니다.
map[i][j] = (input.charAt(j) == '1');
}
}
📌dfs 탐색
집을 발견할 때마다 dfs로 탐색하려 합니다.
이 때 집이 총 몇 개인지 갯수를 세기 위해 dfs 함수가 집의 갯수를 저장한 int 값을 반환하도록 만듭니다.
또한 앞서 말씀드린 것처럼 map[][]는 dfs 중복 탐색을 방지하기 위해 방문 여부를 체크하는 용도로도 사용하겠습니다.
추후 집의 위치 정보를 다시 사용할 필요가 없기 때문에, 굳이 2차원 배열을 새로 선언해서 메모리를 추가로 사용하는 게 아니라
기존의 map[][]의 값을 곧바로 false 로 바꿔버릴 것입니다.
static int dfs(int r, int c){
// 현재 위치의 map값을 false로 바꿔 중복 방문을 방지합니다.
map[r][c] = false;
int nr, nc;
// 단지 안에 속한 집의 총 갯수를 저장할 int 변수입니다. 현재 위치에 집이 하나 있었으니 1로 초기화합니다.
int houses = 1;
for (int dir = 0; dir < 4; dir++) {
// 4방 델타 탐색
nr = r + dR[dir];
nc = c + dC[dir];
if(isInBound(nr, nc)){
// 집이 존재하는 좌표에 대해 dfs 탐색을 재귀적으로 실행합니다.
// 각각의 탐색 결과 집이 총 몇 개였는지 houses에 저장하겠습니다.
houses += dfs(nr, nc);
}
}
// houses의 총합을 결과값으로 반환하고 탐색을 종료합니다.
return houses;
}
static boolean isInBound(int r, int c){
return r >= 0 && c >= 0 && r < N && c < N && map[r][c];
}
📌PriorityQueue를 사용한 정답 값의 오름차순 정렬
방문하지 않은 집을 발견할 때마다 단지 수를 증가시키고, dfs 결과를 PQ에 저장합니다.
PQ에 저장된 정수 값들은 자동으로 오름차순 정렬되어서 저장될 것입니다.
// 단지의 갯수를 저장할 int변수, 단지별 집의 갯수를 정렬해서 저장할 PQ입니다.
int answer = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if(map[r][c]){
// 아직 방문하지 않은 집을 발견할 때마다 단지 갯수를 1 증가시킵니다.
answer++;
// 그 후 dfs 탐색을 실행하고, 결괏값을 즉시 PQ에 저장합니다.
pq.offer(dfs(r, c));
}
}
}
StringBuilder sb = new StringBuilder();
// 단지의 갯수를 StringBuilder에 저장합니다.
sb.append(answer).append('\n');
while(!pq.isEmpty()){
// PQ에서 오름차순으로 정렬된 단지별 집의 갯수를 순서대로 뽑아내, StringBuilder에 저장합니다.
sb.append(pq.poll()).append('\n');
}
// StringBuilder를 출력합니다.
System.out.print(sb);
제출 결과
보통 백준에서 문제 하나를 풀 때마다 한 분 정도 찾아와서 조회해 주시는데,
이번 문제 풀이는 4달 동안 30명 가까운 분들이 조회해 주셨습니다.
많은 분들께 참고가 된 것 같아 이렇게 직접 해설을 올리게 되었습니다.
코드와 관련된 피드백이나 질문이 있으시면 댓글 부탁드립니다.
'Algorithm' 카테고리의 다른 글
[백준][JAVA] 2504 - 괄호의 값 (0) | 2024.07.16 |
---|---|
[백준][JAVA] 3273 - 두 수의 합 (0) | 2024.07.08 |
[백준][JAVA] 3190 - 뱀 (0) | 2023.03.09 |
[Leetcode][Java] 투 포인터로 더욱 빠른 배열 연산을 수행해 보자(2) (2) | 2022.09.24 |
[Leetcode][Java] 투 포인터로 더욱 빠른 배열 연산을 수행해 보자(1) (0) | 2022.09.18 |