[백준] 단지번호 붙이기 (BufferedReader, DFS, ArrayList, 2667번, Java)

qjqjs

 

문제설명

입력 & 출력

나의 풀이

---

먼저 이번 문제는 정사각형 N(지도의 크기)이 주어질 때 집이 있는 곳은 1 없는 곳은 0입니다. 이때 연결되어 있는 집을 단지로 구분하여 단지의 수와 크기를 출력하는 문제입니다.

 

 

먼저 가독성을 높이기위하여 계속 사용되는 변수들을 전역 변수로 선언해주고, 단지가 몇 개인지 모르기 때문에 동적으로 크기를 조절할 수 있도록 ArrayList를 초기화해줍니다.

 

또한 상하좌우로 이동할 것이기 때문에 dx와 dy를 초기화해 줍니다.

 

주석을 달아놔서 따로 설명은 필요 없을 것 같습니다. 

 

 

먼저 DFS를 동작할 함수를 선언합니다.

 

현재 위치를 방문했음을 표시하기 위해 해당 위치를 `true`로 설정하고, 단지 내 집의 수를 나타내는 `count`를 증가시킵니다.

 

그다음, 상하좌우로 이동하기 위해 4번 반복하는 반복문을 작성하는 데 반복문 내에서 현재 위치 `x`와 `y`에 각각 `dx`와 `dy` 값을 더하여 다음 위치를 `nextX`와 `nextY`로 저장합니다.

 

범위를 지정하지 않으면 무한 루프에 빠질 수 있으므로, 배열의 범위를 벗어나지 않도록 제한을 설정해야 합니다. 그리고 다음 위치가 아직 방문하지 않았으며, 집이 있는 경우(1) 다음 위치로 재귀 호출을 수행합니다.

 

 

main문에서는  빠른 입력을 받기 위해서 BufferedReader클래스를 사용하여 입력을 받아줍니다. 방문 여부를 확인할 visited배열과 지도 map의 크기를 입력받은 크기 N만큼 초기화해 줍니다.

 

그다음 50번째 줄에서 지도의 정보를 입력받아 map에 각 요소에 저장을 해줍니다. 이때 각 요소에 접근하기 위해서charAt() 메서드를 사용했기 때문에 '0'을 빼줘서 숫자로 만들어줘야 합니다.❗️

 

그다음 58번째 줄에서 모든 좌표를 탐색하는 데 이 때도 똑같이 방문을 하지 않았으며, 집이 있는 경우(1) 단지 내의 집의 수를 초기화시켜주고, dfs함수를 호출합니다.

 

이 때 만약에 60번째 줄처럼 조건문을 하지 않으면  왼쪽 그림처럼 당연히 N*N 즉 총 단지수가 나오게 됩니다.

 

호출 후 전역변수 count에 담긴 단지 내 집의 수를 최종 리턴할 리스트에 추가를 해줍니다.

 

이렇게 동작하면 방문하지 않은 집이 있는 경우, 인접한 집의 단지 수를 구할 수 있습니다. 또한 새로운 단지가 나타날 때마다 단지 내의 집의 수를 초기화하기 때문에 `count`는 누적되지 않고 각 단지의 개별적인 집의 수를 구할 수 있습니다.

 

 

마지막으로 각 단지의 수가 저장되어 있는 result리스트를 오름차순(Default값)으로 정렬해 주고, size() 메서드를 사용하여 전체 단지 의 수를 출력하고, 향상된 for문을 사용하여 각 단지의 수를 오름차순으로 출력하여 마무리해 줍니다.

 

 

참고❗️

[JAVA] 입출력, BufferedReader, StringTokenizer, StringBuilder 알아보기

[JAVA] ArrayList 알아보기 (동적 배열)