[JAVA / 자바] 백준 2667번 - 단지번호붙이기

 문제 

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선 상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

---

 입력 

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그다음 N 줄에는 각각 N개의 자료(0 혹은 1)가 입력된다.

---

 출력 

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지 내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

---

---

 문제 접근 방법 

STEP 1. 제일 먼저 배열을 두 개를 선언해준다.

배열 1) 입력을 저장하는 배열

배열 2) 단지를 찾으면 단지 숫자를 알려주는 배열

 

STEP 2. 단지를 카운트해줄 전역 변수를 하나 선언한다.

전역 변수로 단지를 카운트해주는 정수형 변수를 하나 선언해서 단지를 하나 찾을 때마다 단지 번호를 매기고 다음 단지로 넘어가기 전에 +1을 해준다.

 

STEP 3. 단지를 찾는 방법은

배열 1)을 전체 탐색하다가 1이 발견되면 새로운 단지를 찾은 것으로 한다.

이때, 새로운 단지를 찾는 방법이 배열 1)에서 1을 발견하는 것이므로 찾았던 단지를 다시 새로운 단지로 인식하면 안 되므로 발견된 단지는 1이 아닌 다른 수(ex 0)로 바꿔 지도에서 지워준다.

 

STEP 4. 단지를 찾았으면 같은 단지는 해당 단지에 지정된 수로 나타내 준다

배열 2)에 배열 1)에서 있었던 아파트의 동일한 위치에 해당 단지수를 저장해준다.

 

STEP 5. 배열 1)의 모든 탐색이 끝나면(배열 1)에 저장된 숫자가 모두 0이 되면),

배열 2)를 출력해준다.

---

 JAVA 코드 풀이 

 코드 실행 결과 

재귀 Ver. 코드 실행 결과

---

 후기 

같은 단지끼리는 단면이 붙어있다고 했다. 따라서 상하좌우 중 하나가 붙어있는 경우만 같은 단지로 취급한다.

처음에 나는 재귀로 풀었는데 알고 보니 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)문제였어서 추후에 각 버전의 코드를 추가해놓도록 하겠다.

---

 문제 원본 

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

2667번: 단지번호붙이기

 알고리즘 분류 

• 그래프 이론 - [자료구조] 그래프(Graph)의 구현
• 그래프 탐색 - [자료구조] 그래프(Graph) 순회
• 너비 우선 탐색(BFS, Breath First Search) - 추후 추가 예정
• 깊이 우선 탐색(DFS, Depth First Search) - 추후 추가 예정