Danji_알고리즘_sort

오늘 풀어 볼 문제는 단지에 이름 붙이기 문제입니다.

문제는 다음과 같으며 풀기 전 조건을 먼저 생각해야합니다.

단번에 탐색 문제라고 확인할 수 있는데, 탐색할 때의 조건을 어떻게 두면 좋을지 고민해야합니다.

우선 2차원배열 map으로 설정했다고 했을 경우, 1이 나온 곳만 탐색을 시작합니다.

이 중 반복문을 두어서 1이 나온 곳을 파악하고 거기서부터 동서남북으로 탐색을 시작합니다.

더이상 탐색할 곳이 없을 경우 재귀 호출을 리턴하여 멈추게합니다. 

탐색 횟수를 카운트해서 메모리에 추가하고 다음 1이 나온 곳을 찾아서 탐색합니다.

앞서 내용을 반복하면서 카운팅한 변수들을 메모리에 추가하여 반환하면 이 문제는 해결됩니다.

주의할 점은 아래와 같습니다.

---

1. 탐색할 때 기저조건은 탐색할 곳이 더이상 없을 경우가 됩니다.  

따라서 탐색을 순차적으로 진행하다가 더이상 탐색할 곳이 없을 때 자연스럽게 return 하는 것이 기저 조건이 됩니다.

2. 백트래킹 과정을 거치면 안됩니다. 백트래킹은 탐색 과정에서 한 번 갔다가 "아.. 여기는 더이상 갈 곳이 아니구나" 

회귀하여서 가지 않았다고 다시 체크한 뒤 탐색을 진행하는 방법입니다. 

따라서 이 과정을 거치게 된다면, 이론상 횟수가 더 줄기 때문에 우리가 구하려 했던 값이 나오지 않을 것입니다.

3. 한 구간 (한 단지)을 모두 탐색하여 더이상 탐색할 곳이 없을 경우 리턴으로 마무리되면서, 카운트한 횟수도 

메모리에 추가한 뒤 초기화를 해야합니다. 

이유는, 다시 1인 부분을 검색한 뒤 탐색 과정을 새로 시작할 것이기 때문에 

카운트 초기화는필수입니다. 

4. 메모리에 카운트를 추가할 경우, 배열이나 리스트에 추가될텐데, 문제 조건상 오름차순으로 정의되어 있기에 

간단한 Sorting 작업을 통해 메모리 안의 값을 반환해야합니다.

---

우선 1인 부분을 먼저 찾아서 탐색을 하고 카운트를 리스트에 넣고 초기화 하는 코드를 확인하겠습니다.

단! 해당 위치를 이미 방문하지 않았다는 전제하에서 진행해야합니다! 

1인 구간을 이미 방문했는데 다시 검색을 통해 방문한 곳부터 재탐색이 이루어지면 안되기 때문입니다.

---

for(int i=0;i<N;i++){

for(int j=0;j<N;j++){

if(map[i][j] == 1 && visited[i][j] == false){

dfs(map,i,j,visited);

alList.add(count);

count = 0;

}

}

}

---

private static void dfs(int[][] map2, int x, int y, boolean[][] visited2) {

// TODO Auto-generated method stub

visited2[x][y] = true;

count += 1;

if (x > 0) {

if (map2[x - 1][y] == 1 && visited2[x - 1][y] == false) {

dfs(map2, x - 1, y, visited2);

}

}

if (x + 1 < num) {

if (map2[x + 1][y] == 1 && visited2[x + 1][y] == false) {

dfs(map2, x + 1, y, visited2);

}

}

if (y > 0) {

if (map2[x][y - 1] == 1 && visited2[x][y - 1] == false) {

dfs(map2, x, y - 1, visited2);

}

}

if (y + 1 < num) {

if (map2[x][y + 1] == 1 && visited2[x][y + 1] == false) {

dfs(map2, x, y + 1, visited2);

}

}

return;

}

}

---

이제 alList에 추가된 내용을 오름차순으로 정리해야한다.

사실 리스트를 오름,내림 차순으로 정리하는 것은 Comparator패턴을 사용해서 정리해도 된다.

관련된 것은 이 전 포스팅에도 있기 때문에 별도로 언급은 하지 않을 것이다.

하지만 이번에는 리스트 내용을 배열에 넣고 정렬을 사용해서 나열했다.

Selection sort를 사용해서 정렬을 할 것인데 코드는 아래와 같다.

[전체코드]

---

import java.util.ArrayList;

import java.util.Scanner;

public class Danji4 {

private static Scanner scanner;

private static int count;

private static ArrayList<Integer> alList;

private static int[] alArr;

private static int[][] map;

private static boolean[][] visited;

private static int num;

public static void main(String[] args) {

// TODO Auto-generated method stub

scanner = new Scanner(System.in);

num = scanner.nextInt();

map = new int[num][num];

visited = new boolean[num][num];

alList = new ArrayList<>();

for (int i = 0; i < num; i++) {

String str = scanner.next();

for (int j = 0; j < num; j++) {

map[i][j] = (int) (str.charAt(j) - '0');

visited[i][j] = false;

}

}

for (int i = 0; i < num; i++) {

for (int j = 0; j < num; j++) {

if (map[i][j] == 1 && visited[i][j] == false) {

dfs(map, i, j, visited);

alList.add(count);

count = 0;

}

}

}

System.out.println(alList.size());

alArr = new int[alList.size()];

for (int i = 0; i < alList.size(); i++) {

alArr[i] = alList.get(i);

}

// 아래 내용은 선택정렬로 진행한 것으로, 이중 for문에서 한 칸씩 비교하면서 나열할 인덱스 값을 별도의 변수에 저장한 뒤,

// 해당 인덱스로 배열 요소의 값을 SWAP 하는 것이다.

// 버블 정렬은 인덱싱 작업 없이 값을 바로 SWAP 하는 것이라 생각하면 됩니다.

for(int i=0;i<alArr.length - 1;i++) {

int cmp_inx = i;

for(int j=i;j<alArr.length;j++) {

if(alArr[cmp_inx] > alArr[j]) {

cmp_inx = j;

}

int tmp = alArr[i];

alArr[i] = alArr[cmp_inx];

alArr[cmp_inx] = tmp;

}

}

for(int elem : alArr)

System.out.println(elem);

}

private static void dfs(int[][] map2, int x, int y, boolean[][] visited2) {

// TODO Auto-generated method stub

visited2[x][y] = true;

count += 1;

if (x > 0) {

if (map2[x - 1][y] == 1 && visited2[x - 1][y] == false) {

dfs(map2, x - 1, y, visited2);

}

}

if (x + 1 < num) {

if (map2[x + 1][y] == 1 && visited2[x + 1][y] == false) {

dfs(map2, x + 1, y, visited2);

}

}

if (y > 0) {

if (map2[x][y - 1] == 1 && visited2[x][y - 1] == false) {

dfs(map2, x, y - 1, visited2);

}

}

if (y + 1 < num) {

if (map2[x][y + 1] == 1 && visited2[x][y + 1] == false) {

dfs(map2, x, y + 1, visited2);

}

}

return;

}

}

---

감사합니다.