Number of Islands (BFS)

제목만 보면 거창해 보이지만 옛날 포스팅과 마찬가지로 게으름뱅이가 자신의 안타까운 코딩 능력을 체감하고 반성하는 의미에서 적는 글이다.

여기서 다루는 문제는 LeetCode의 Explore 탭에서 제공하는 "Queue and BFS" 챕터에서 풀어볼 수 있는 문제 "Number of Islands"다.

https://leetcode.com/explore/learn/card/queue-stack/231/practical-application-queue/1374/

Account Login - LeetCode

문제는 아래와 같다.

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

 

Example 1:

Input: grid = [ ["1","1","1","1","0"], ["1", "1", "0", "1", "0"], ["1", "1", "0", "0", "0"], ["0", "0", "0", "0", "0"] ]

Output: 1

 

Example 2:

Input: grid = [ ["1","1","0","0","0"], ["1", "1", "0", "0", "0"], ["0", "0", "1", "0", "0"], ["0", "0", "0", "1", "1"] ]

Output: 3

 

즉, 1(땅)과 0(바다)로 그려진 맵에서 섬의 개수를 파악하는 문제로 챕터에서 볼 수 있듯이 BFS를 활용하는 것이 문제의 의도였다. 상하좌우 4방향에 땅이 이어져 있어야 한 대륙으로 치며 대각선에만 땅이 있다면 같은 대륙, 즉 같은 섬으로 인정되지 않는다. 위의 예시에서 주어진 지도를 그리면 다음과 같다.

11110

11010

11000

00000

숫자 1이 이어진 모습을 보면 모두 이어져 있기 때문에 결과적으로 섬은 하나만 존재하게 된다.

11000

11000

00100

00011

두 번째 예시의 경우 3번째 줄에서 혼자 고립되어 있는 1처럼 상하좌우로 땅이 이어져 있지 않다면 같은 섬으로 인정되지 않는다. 즉 섬이 3개가 존재하는 것을 볼 수 있다.

 

그렇다면 이를 어떻게 BFS로 풀어낼 수 있을까? 사실 여기서부터 난관이었다. 정말 몇 달만에 온라인 저지에 도전하는 것이라곤 해도 프로그래밍을 열심히 하지 않았다 보니 대부분의 언어를 기초적인 내용 말고는 다 까먹은 상태였는데, 그나마 알 것 같은 자바를 사용해보려고 해도 메서드가 하나도 기억나지 않아 정말 막막했던 것 같다. 일부러 IDE를 쓰지 않고 레퍼런스를 찾아보면서 진행해서 더욱 그럴지도 모른다.

 

학교에서 배웠던 내용으로만 생각하면 그래프 자료구조에서 루트 노드부터 시작해서 자식 노드를 큐에 등록하면서 하나하나 탐색한다는 이론적인 원리는 알 수 있겠지만 그래프 자료구조가 아니라면? 사실 모든 데이터가 그래프 자료구조로 제공되는 것도 아니고 문제에서 주어진 특정 자료구조에 대해서 자료구조 내 데이터들끼리의 연결을 그래프화해야 하기 때문에 문제를 어떻게 정의하는지부터 고민에 빠지게 되었다.

 

조건이 그렇게 복잡하진 않은 편이라 현재 셀의 상하좌우셀이 그래프에서 자식 노드라는 컨셉으로 문제를 정의했다. 즉 문제를 보이는 그대로 2차원 배열로 보는 것이 아니라 첫 번째 노드(셀)에서 직각으로 뻗어나가는 자식 노드(셀)를 가진 그래프 형식으로 생각했다.

그렇다면 총 몇개의 섬이 있는가를 어떻게 구할 수 있을까? 한 번의 BFS 탐색에서는 가능한 모든 1을 탐색하면서 섬을 찾아내는 만큼 몇 번의 BFS 탐색이 호출되었는지가 섬의 개수와 동일한 의미를 가진다는 것을 알 수 있다. 그래서 BFS 탐색을 함수 화하여 호출시마다 카운트 값을 증가시키는 방법으로 섬의 개수를 셀 수 있으며 한번 섬을 찾은 후에는 다시 다른 셀을 일일이 검사하면서 섬을 찾는 과정을 반복해야 한다.

 

탐색에서 중요한 조건인 한번 방문한 노드는 다시 방문하지 않는다는 것에 유의해야 할 것이다. 위의 그림에서 볼 수 있듯이 (0, 0) 셀에서 섬을 찾아낸 후 다시 다른 셀(여기서는 바로 옆 셀)을 조사할 때 이미 조사한 셀임을 확인하지 못한다면 다시 섬을 탐색하는 중첩이 발생할 수 있기 때문이다. 그래서 주어진 배열과 동일한 크기의 배열을 선언해서 탐색 여부를 저장해두어야 할 것이다.

 

한 셀에서 상하좌우 셀을 모두 검사하기 때문에 배열의 셀들을 어떤 방향으로 검사하는지는 결과에 영향을 끼치지 않는다. 하지만 배열 자체를 벗어나서 인덱싱하지 않도록 예외처리가 필요할 것이다. 이는 큐에 넣을 때 검사해서 넣거나 넣은 후 값을 뺄 때 검증하는 두 가지 방법을 사용할 수 있다.

 

그렇다면 이 노드를 어떻게 큐에 넣을 수 있을까? 사실 이 부분에서 제일 크게 고민해서 결국 인터넷 검색을 통해 해결하게 되었다. 문제에서 주어지는 배열은 char형 배열로써 각 원소는 0, 1 값을 가진다. 이는 기존의 그래프 자료구조에서 사용하던 노드 클래스가 아니기 때문에 자식 노드나 부모 노드 같은 멤버 변수를 가지지도 않는 단순 자료형이다. 그래서 배열의 좌표를 구현하려면 한 쌍의 데이터를 보관할 수 있는 자료구조가 필요했다. 이에 대해서 좋은 방법이 없을까 고민하던 도중 다른 알고리즘 사이트에서 제시한 해설에서 다음과 같은 코드를 보고 해결할 수 있었다.

 ...
 	queue.add(i + "," + j);
 ...
 
 ...
 	String x = queue.remove();
    int row = Integer.parseInt(x.split(",")[0]);
    int col = Integer.parseInt(x.split(",")[1]);
...

즉 좌표값을 문자열로 포맷하여 추후 파싱을 통해 이를 분리해내는 것이었다. 무조건 HashMap이나 Set 같은 자바의 자료구조를 사용하려고만 생각했던 내 생각의 짧음을 반성할 수 있게 되는 계기였다.

 

이를 기반으로 작성한 코드는 다음과 같다.

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public static int rows = 0;
    public static int cols = 0;
    
    public int numIslands(char[][] grid) {
        int numOfIslands = 0;
        rows = grid.length;
        if(rows == 0) return 0;
        cols = grid[0].length;
        
        boolean[][] gridVisit = new boolean[rows][cols];
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                gridVisit[i][j] = false;
            }
        }
        
        Queue<String> queue = new LinkedList<>();
        
        for(int row=0;row < rows;row++){
            for(int col=0;col < cols;col++){
                if(gridVisit[row][col] == true || grid[row][col] == '0') continue;
                queue.add(row + "," + col);
                BFS(grid, queue, gridVisit);
                numOfIslands++;
            }
        }
        
        return numOfIslands;
        
    }
    
    public void BFS(char[][] grid, Queue<String> queue, boolean[][] gridVisit){
        
        while(queue.isEmpty() == false) {
            String coord = queue.remove();
            int row = Integer.parseInt(coord.split(",")[0]);
            int col = Integer.parseInt(coord.split(",")[1]);
            if(gridVisit[row][col] == true) continue;
            else gridVisit[row][col] = true;


            if(row > 0 && grid[row-1][col] == '1'){
                queue.add((row-1) + "," + col);
            }

            if(row < rows-1 && grid[row+1][col] == '1'){
                queue.add((row+1) + "," + col);
            }

            if(col > 0 && grid[row][col-1] == '1'){
                queue.add(row + "," + (col-1));
            }

            if(col < cols-1 && grid[row][col+1] == '1'){
                queue.add(row + "," + (col+1));
            }
        }
    }
}

결과는 다른 사용자들보다 약 25%정도 앞선 그다지 만족스럽지 못한 결과가 나왔지만 오랜만에 다시 잡은 온라인 저지에서 문제를 해결한 것에 의의를 두고자 한다.

 

[출처 | https://algorithms.tutorialhorizon.com/number-of-islands-using-bfs/]