Baekjoon 2667 단지번호붙이기 JAVA

해당 문제는 어제 풀었던 유기농 배추와 비슷한 문제다.

https://blog.naver.com/soonil0119/222304647310

Baekjoon 1012 유기농 배추 JAVA

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

2667번: 단지번호붙이기

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%202667DFS

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

BFS 버전

https://github.com/JUNGSOONIL/JAVA/commit/3b8a367c6842f051101be8213da99410d6e8f541

Create BAEKJOON 2667BFS · JUNGSOONIL/JAVA@3b8a367

 

해당 문제는 집의 위치를 알려주면 해당 집을 단지로 묶고 단지의 총개수와 단지별 집수를 오름차순으로 출력해 주는 문제다.

​

조건

단지 = 연결된 집의 모임

연결 조건 = 상 하 좌우 중 다른 집이 있는 경우, 대각선 집은 X

단지의 집수를 오름차순으로 정렬

​

처음에 해당 문제는 집의 여부를 한 줄로 받다 보니 고민을 했던 문제인데 String 변수에 한 줄로 입력받고 charAt()를 이용하여 하나씩 잘라준 뒤 문자 0,1을 숫자 0,1로 바꿔주기 위해 str.charAt(j) - '0'을 하여 집의 위치를 저장해 준다.

​

이후 해당 집이 있고 해당 집을 방문하였는지를 판단하여 방문하지 않았으면 DFS를 실시하고 단지 수 1 증가시켜준다.

​

DFS에서는 먼저 해당 집을 방문한 것으로 표시하고 해당 단지 내 집수를 1증가 시킨 후 상하좌우 중 집이 있는지를 확인하고 집이 있다면 해당 집을 DFS 해서 반복하여 준 뒤 집이 더 이상 없다면 DFS를 빠져나온다

​

위와 같은 방법으로 모든 집을 방문하고 나면 단지 내 집 수 배열인 co를 정렬해 주고 데이터가 입력된 곳만 출력해 주면 문제를 해결할 수 있다.