![[백준,BOJ 2667] 단지번호붙이기(JAVA 구현,추가풀이)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FUFuq6%2FbtqzI3Cch61%2FdlybSo5djwbH5lfROfmmN1%2Fimg.png)
반응형
-내 생각
DFS, BFS카테고리에 분류되어 있는 문제인 단지 번호 붙이기이다. 이제 막 DFS, BFS를 공부하기 시작한 입장에서 이게 어떻게 하면 DFS와 BFS를 이용하여 풀 수 있는 거지..?라는 생각이 들었다. 아마도 응용력이 많이 부족한 듯싶다. 그래서 다른 블로그 분들의 풀이를 한 번 분석해봤는데, 대다수가 주석처리가 많이 되어있지 않아 이해하는데 어려움이 많았다. 그래서 일단 되는데 까지 해보자 했는데 진짜 됐다.. 기분 좋아 ㅎㅎ
-해법
이 문제 같은 경우에는 한 칸에 1이 존재한다면 주변에 1의 수만큼 카운트를 올려준 후 별도의 공간에 저장 후 오름차순 출력을 하면 되는데, 문제는 주변에 1의 수를 어떻게 셀 것인가가 관건이었다. 개인적인 생각으로는 내가 푼 방법이 DFS인지는 모르겠지만, DFS와 비슷하게 재귀를 이용해서 방문 배열을 동일하게 만든 후 모든 칸을 탐색하면서(DFS가 완전 탐색의 한 종류이기 때문에) 1을 발견하는 순간부터 인접한 1을 깊이 우선 탐색과 같은 방식으로 탐색해나가면서 인접한 1이 없을 때까지 탐색 후 다시 재귀를 종료시켜 인접한 1이 있는 곳까지 돌아오는 과정을 카운트를 세어주었다. 그리고 각 단지별로 카운트를 어레이 리스트에 저장해둔 후 오름차순 출력해주었다.
import java.util.*;
public class Main {
static int node[][]; // 아파트 단지 배열
static int check[][]; // 각 아파트 단지 방문여부 배열
static int cnt =1;
static ArrayList<Integer> array = new ArrayList<>(); // 각 단지의 수를 저장 할 어레이 리스트
static void dfs(int x,int y) { //DFS 메소드 , 아파트 단지 배열에서 각 점을 인자로 전달
check[x][y] =1; // 전달 된 인자는 방문했으므로 1저장
// cnt변수는 1로 초기화했기 때문에 별도의 증가는 필요없다.
//기준열의 오른쪽열을 확인해야 하므로 범위에서-1, 오른쪽열이 1이면서 방문하지 않은 곳이면
if( y<node.length-1 && node[x][y+1]==1 && check[x][y+1]!=1) {
cnt++; // cnt변수 증가
dfs(x,y+1); // 이후 오른쪽열로 이동
}
//기준행의 아랫쪽행을 확인해야 하므로 범위에서-1, 아랫쪽행이 1이면서 방문하지 않은 곳이면
if(x<node.length-1 && node[x+1][y]==1&& check[x+1][y]!=1) {
cnt++; // cnt변수 증가
dfs(x+1,y); // 이후 아랫쪽으로 이동
}
//기준열의 왼쪽열을 확인해야 하므로 0보다 커야하며, 왼쪽열이 1이면서 방문하지 않았다면
if(y>0 && node[x][y-1]==1&& check[x][y-1]==0) {
cnt++; // cnt변수 증가
dfs(x,y-1); // 이후 왼쪽으로 이동
}
//기준행의 윗쪽행을 확인해야 하므로 0보다 커야하며, 윗쪽행이 1이면서 방문하지 않았다면
if(x>0 && node[x-1][y]==1&& check[x-1][y]==0) {
cnt++; // cnt변수 증가
dfs(x-1,y); // 윗쪽행으로 이동
}
// 기준행을 기준으로 방문하지 않은 곳이면서 1의 값을 가지는 곳을 상,하,좌,우로 살펴보는 과정이다.
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n= sc.nextInt(); // 지도의 크기 n
node = new int[n][n]; // 지도 배열
check = new int[n][n]; // 지도 방문배열
for(int i=0;i<node.length;i++) {
String row=sc.next();
for(int j=0;j<node[i].length;j++) {
node[i][j] = row.charAt(j)-'0';
}
}
for(int i=0;i<node.length;i++) {
for(int j=0;j<node[i].length;j++) {
if(node[i][j] == 1 && check[i][j]==0) { // 1의값이면서 방문하지 않은 곳의 정보만 전달
cnt =1; // cnt변수 초기화
dfs(i,j);// 지도의 (0,0)부터 전달
array.add(cnt); // 단지의 수를 어레이 리스트에 저장
}
}
}
System.out.println(array.size()); // 단지의 개수
Collections.sort(array); // 각 단지의 아파트 수 정렬
for(int i=0;i<array.size();i++) {
System.out.println(array.get(i));
}
}
}
이전에 풀었던 풀이는 DFS를 이용한 깊이 우선 탐색을 사용하였다. 이번 풀이는 BFS를 이용한 너비 우선 탐색방법으로 한 좌표 기준으로 상, 하, 좌, 우에 1이 존재하는지 여부를 확인해야 하기 때문에 인접한 노드를 탐색하는 BFS가 적당하다고 생각 들었다.
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Dot{ // X,Y 좌표를 저장하는 클래스
int x;
int y;
public Dot(int x, int y) {
super();
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
}
class Main {
static ArrayList<Integer> count = new ArrayList<>();
static int dx[] = {1,-1,0,0}; // 상, 하, 좌, 우를 탐색하기 위한 배열
static int dy[] = {0,0,1,-1};
// BFS 탐색 메소드
static void bfs(int[][] a, boolean[][] check, Dot d) {
// 전달받은 좌표부터 주변의 집 좌표를 저장 할 큐
Queue<Dot> q = new LinkedList<>();
int cnt = 0; // 주변에 존재하는 집의 수를 저장 할 변수
q.offer(d); // 초기 전달받은 좌표를 큐에 우선 삽입
check[d.getX()][d.getY()] = true; // 해당 좌표 방문 표시
while(!q.isEmpty()) { // 주변의 집이 존재하지 않을 때 까지 반복
Dot d_p = q.poll(); // 전달받은 좌표 값
int x = d_p.getX();
int y = d_p.getY();
cnt++; // 주변 집의 수만큼 반복되므로 cnt 증가
for(int i=0;i<4;i++) { // 상, 하, 좌, 우 탐색
// 각 값의 계산에 따라 상, 하, 좌, 우의 좌표가 저장되며 반복
int nx = x + dx[i];
int ny = y + dy[i];
// 맵의 범위를 벗어나는 좌표는 무시
if(nx>=a.length || nx<0 || ny>=a[nx].length || ny < 0) continue;
// 이미 방문한 적 있는 집은 무시
if(check[nx][ny]) continue;
// 상, 하, 좌, 우에 집이 존재하는 경우
if( a[nx][ny] == 1){
check[nx][ny] = true; // 방문처리 후
q.offer(new Dot(nx,ny)); // 해당 집의 좌표를 큐에 넣어준 뒤 계속해서 탐색
}
}
}
// 모든 과정이 끝나면 주변에 더 이상 방문하지 않은 집이 없다는 의미로 ArrayList에 집의 수를 삽입
count.add(cnt);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(); // 맵의 크기
int a[][] = new int[n][n]; // N X N 크기의 맵
boolean check[][] = new boolean[n][n]; // N X N 크기의 방문여부 배열
for(int i=0;i<a.length;i++) { // 단지 정보 입력
String str = in.next();
for(int j=0;j<a[i].length;j++) {
a[i][j] = str.charAt(j)-'0';
}
}
Dot d; // BFS 탐색을 시작할 위치 정보를 담을 객체
for(int i=0;i<a.length;i++) {
for(int j=0;j<a[i].length;j++) {
if(a[i][j] == 1 && check[i][j] == false) { // 맵을 탐색하다 단지가 위치하면서 방문하지 않았다면
d = new Dot(i,j); // 좌표 정보 객체를 생성해
bfs(a,check,d); // 해당 좌표부터 너비 우선 탐색을 수행
}
}
}
System.out.println(count.size()); // 각 단지의 수는 ArrayList의 size
Collections.sort(count); // 오름차순 출력을 위한 정렬
for(int i =0; i<count.size();i++) { // 각 단지의 집 수를 출력
System.out.println(count.get(i));
}
}
}초기에 풀이할 때 모든 좌표를 BFS를 이용해 탐색하고자 하였는데, 각 단지의 집들을 카운팅하는 과정이 복잡해져 초기에 맵을 탐색 하며 최초로 방문하지 않은 집의 좌표를 기점으로 BFS 탐색을 수행하는 방식을 사용하게 되었다.
반응형