Java 알고리즘 DFS 섬 개수 구하기

 

오늘은 DFS를 활용하여 입력받은 격자판에서 섬의 개수를 구하는 문제를 풀어보려고 합니다😊

DFS BFS 섬나라

 

개요

문제 내용

 

문제 예시

이번 문제의 핵심은 DFS 알고리즘 활용, 8가지 방향으로 이동하는 방법, 섬을 만났을 때 체크, 출발점 체크 총 4가지가 될 것 같네요😀

 

Setting📙

public class Island {
    static int result = 0, n;
    static int[] dx = {-1, -1, 0 ,1 ,1 ,1, 0, -1};
    static int[] dy = {0 ,1 ,1 ,1, 0, -1, -1, -1};

    public static void main(String[] args) {
        Island T = new Island();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int[][] arr = new int[n][n];
        for(int i = 0; i < n ; ++i) {
            for(int j = 0; j < n; ++j) {
                arr[i][j] = sc.nextInt();
            }
        }
        T.solution(arr);
        System.out.println(result);
    }
}

static으로 선언 된 result는 섬의 개수를 뜻하고, n은 격자판의 행,열 사이즈를 뜻합니다. 

 

static으로 선언 된 dx, dy는 각각 상자판에서 세로, 가로축을 의미하여 이 둘을 조합하여 상하좌우 및 대각선 총 8가지 방향을 바라볼 때 사용됩니다. 이 부분은 DFS 함수에서 설명드릴게요.

 

main에서는 Scanner를 통해 예제 값인 7을 입력받았습니다. arr 배열을 만들어서 7 * 7의 격자판을 생성해 줍니다. 그리고 이중 반복문을 통해 격자판에 들어갈 숫자들을 입력받았습니다.

 

그리고 하단에서 만들 solution을 호출하였습니다😊

 

Solution📘

public void solution(int[][] board) {
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            if(board[i][j] == 1) {
                result++;
                board[i][j] = 0; // 출발점 0으로 초기화
                DFS(i, j, board);
            }
        }
    }
}

Solution은 간단합니다. 모든 격자판을 탐색한다고 보시면 되는데, 문제 상에서 1이 섬에 해당하기 때문에 이중 반복문을 이용하여 격자판을 탐색하면서 해당 격자가 1일 때 즉, 섬의 일부를 만났을 때를 조건으로 걸어줍니다.

 

섬의 일부를 만났기 때문에 섬의 개수를 뜻하는 result는 증가시켜 주고, 다시 그 격자를 밟지 않기 위해서 해당 격자를 0으로 초기화시켜줍니다.

 

그리고 DFS 함수를 실행시킵니다😄

 

📌 문제 예시 상 맨 처음 (0,0)에서 시작하게 되는데, 해당 격자 중심으로 8가지 방향을 확인하면서 1(섬의 일부)을 만났을 때를 다 0으로 초기화시킵니다. 그러면 해당 섬은 모두 0으로 초기화되고, 다음 격자들을 살피면서 섬의 일부를 만날 때마다 해당 섬의 모든 1을 0으로 뭉텅이 식으로 바꿔가는 과정입니다.

 

DFS📒

public void DFS(int x, int y, int[][] board) {
    for(int i = 0; i < 8; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx >= 0 && nx < n && ny >= 0 && ny < n
                && board[nx][ny] == 1) {
            board[nx][ny] = 0;
            DFS(nx, ny, board);
        }
    }
}

DFS는 위에서 언급했듯이 섬의 일부를 만났을 때(시작점) 해당 섬의 모든 곳을 0으로 초기화시켜주는 역할을 합니다. 반복문을 통해 상하좌우 및 대각선을 탐색하는데, nx와 ny는 배열을 더해보시면 12시 방향부터 시계방향으로 체크하는 것을 확인하실 수 있을 겁니다.

 

조건문으로는 0 이상 n(문제 상 7) 미만이어야 하는대, 격자판 테두리에 있는 격자들은 격자판 외부를 쳐다볼 수 있기 때문에 설정하였습니다(= 격자판 외부를 쳐다보지 못하게 막는 역할) 또한, 섬의 일부가 아닌 곳을 바라볼 필요가 없기 때문에 바라보는 격자가 1이어야만 합니다. 

 

조건문을 통과했다는 얘기는 이어진 섬을 만났다는 얘기이기 때문에, 다시금 그곳을 바라보지 못하게 0으로 초기화시켜주고 재귀적으로 DFS를 호출시킵니다😄

 

Result📗

테스트 결과

입력 예시에 맞게 Scanner를 통해 입력하니 섬의 개수 5를 출력하는 것을 확인할 수 있었습니다.

 

 

---

👨‍👩‍👦‍👦 오픈채팅방 운영

취업을 준비하는 예비 개발자분들을 위한 질문&답변할 수 있는 공간을 만들었습니다. 취업과 이직을 하기 위해서 어떤 걸 중점적으로 준비해야 하는지부터 포트폴리오&이력서 작성법 등 다양한 질문들을 받고 답변을 드립니다. 참여하셔서 다양한 정보 얻고 가시면 좋을 것 같네요😁

 

참여코드 : 456456

https://open.kakao.com/o/gVHZP8dg

비전공 개발자 취업 준비방(질문&답변)

 

---

👨‍💻 전자책 출간

아울러 제가  🌟비전공자에서 2년만에 보안 전문 중견기업으로 이직 한 방법들을 정리한 전자책을 출간 하게 되었습니다. 어떤 걸 공부해야 하는지, 이직을 위해서 무엇을 준비해야 하는지, 제가 받았던 기술 면접 리스트 등 다양한 목차로 구성되어 있습니다. 또한, 구매 시 1:1 채팅을 이용하여 포트폴리오 첨삭을 도와드리고 있습니다. 🐕전자책으로 얻은 모든 수익은 유기견 센터 '팅*벨 입양센터'에 후원될 예정입니다. 관심 있으신 분들은 아래 링크를 참고해주세요😁

https://kmong.com/gig/480954

비전공개발자 2년만에 중견기업 들어간 방법 | 14000원부터 시작 가능한 총 평점 0점의 전자책, 취

---

 

마치며

지금까지 DFS를 활용해서 섬의 개수를 구해보았습니다. 다음 포스팅도 DFS를 활용해서 거리를 구하는 문제를 풀어볼까 합니다. 다음 포스팅에서 뵐게요😄