[백준 알고리즘] Q2667 단지번호 붙이기 (Recursive)

1. Java 구현

package recursive;
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
    	/* 1. 입력 받기! */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        char[][] arr = new char[n][n];
        for (int i = 0; i < n; i++) {
            arr[i] = br.readLine().toCharArray();
        }

        /* 해당위치를 접근했는지 확인을 위해 사용! */
        boolean[][] visited = new boolean[arr.length][arr[0].length];
        int cnt = 0;
        /* 결과값을 받으면, 오름차순으로 정렬이 필요하기 때문에 결과값을 저장하는 용도로 사용! */
        List list = new ArrayList<>();
        for(int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                if(arr[j][i] == '1' && visited[j][i] == false) {
                    cnt++;
                    list.add(findBlock(j, i, arr, visited) + 1);
                }
            }
        }
        
        Collections.sort(list);
        bw.write(cnt + "\n");
        for(int num : list)
            bw.write(num + "\n");

        bw.close();
        br.close(); 
    }

    public static int findBlock(int y, int x, char[][] arr, boolean[][] visited) {
        int cnt = 0;
        visited[y][x] = true;
        if(x > 0 && arr[y][x - 1] == '1' && !visited[y][x - 1])
            cnt += (findBlock(y, x - 1, arr, visited) + 1); // 좌이동

        if(x < arr.length - 1 && arr[y][x + 1] == '1'  && !visited[y][x + 1])
            cnt += (findBlock(y, x + 1, arr, visited) + 1); // 우이동

        if(y > 0 && arr[y - 1][x] == '1'  && !visited[y - 1][x])
            cnt += (findBlock(y - 1, x, arr, visited) + 1); // 위 이동

        if(y < arr.length - 1 && arr[y + 1][x] == '1' && !visited[y + 1][x])
            cnt += (findBlock(y + 1, x, arr, visited) + 1); // 아래 이동

        return cnt;
    }
}

2. 코드 설명

 재귀함수를 이용해서 길을 찾았다. 이미 방문했던 위치를 확인하기 위한 배열을 생성했다. 배열은 확인유무만 확인하면 되기 때문에 boolean 타입이고,

 배열의 크기는 단지 배열과 동일한 크기로 설정했다. 이동은 위, 아래, 좌, 우 4방향으로만 이동이 가능하다. 예를들어, 좌측에 방문하지 않았고, 좌측에 아파트가 

 있으면 좌측이 이동가능하다. 그러나 좌측을 방문한 경험이 있다면 이동하지 않는다. 이와같이 4방향으로 이동할 수 있고, 이동할 곳이 없으면 탈출되도록 했다.

 

3. Pain Point

 그리고 배열을 이용할 때, 일반적으로는 x, y 순서이지만.. 배열은 반대라서 헷갈렸다 ..

 함수를 보면 재귀인가? 아니면 그냥 반복문인가? 애매할지 모른다. 나도 구현을 하면서 애매하다는 것을 느꼇다..

 그렇다는 것은 아직 공부가 부족하다는 것 같다..