-
해당 문제는 어제 풀었던 유기농 배추와 비슷한 문제다.
https://blog.naver.com/soonil0119/222304647310
https://www.acmicpc.net/problem/2667
https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%202667DFS
BFS 버전
https://github.com/JUNGSOONIL/JAVA/commit/3b8a367c6842f051101be8213da99410d6e8f541
해당 문제는 집의 위치를 알려주면 해당 집을 단지로 묶고 단지의 총개수와 단지별 집수를 오름차순으로 출력해 주는 문제다.
조건
단지 = 연결된 집의 모임
연결 조건 = 상 하 좌우 중 다른 집이 있는 경우, 대각선 집은 X
단지의 집수를 오름차순으로 정렬
처음에 해당 문제는 집의 여부를 한 줄로 받다 보니 고민을 했던 문제인데 String 변수에 한 줄로 입력받고 charAt()를 이용하여 하나씩 잘라준 뒤 문자 0,1을 숫자 0,1로 바꿔주기 위해 str.charAt(j) - '0'을 하여 집의 위치를 저장해 준다.
이후 해당 집이 있고 해당 집을 방문하였는지를 판단하여 방문하지 않았으면 DFS를 실시하고 단지 수 1 증가시켜준다.
DFS에서는 먼저 해당 집을 방문한 것으로 표시하고 해당 단지 내 집수를 1증가 시킨 후 상하좌우 중 집이 있는지를 확인하고 집이 있다면 해당 집을 DFS 해서 반복하여 준 뒤 집이 더 이상 없다면 DFS를 빠져나온다
위와 같은 방법으로 모든 집을 방문하고 나면 단지 내 집 수 배열인 co를 정렬해 주고 데이터가 입력된 곳만 출력해 주면 문제를 해결할 수 있다.
728x90'알고리즘 > Baekjoon' 카테고리의 다른 글
Baekjoon 17478 재귀함수가 뭔가요? JAVA (0) 2021.11.06 Baekjoon 11052 카드 구매하기 JAVA (0) 2021.11.06 Baekjoon 15988 1, 2, 3 더하기 3 JAVA (0) 2021.11.05 Baekjoon 1012 유기농 배추 JAVA (0) 2021.11.05 Baekjoon 2606 바이러스 JAVA (0) 2021.11.05 댓글