[DFS]LeetCode 200번. 섬의 개수

1. 문제

1을 육지로, 0을 물로 가정한 2D 그리드 맵이 주어졌을 때, 섬의 개수를 계산하라.

(연결되어있는 1의 덩어리 개수를 구하라)

 

 

제약

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j]'0'또는 입니다 '1'.

 

 

2. 풀이

1) 왜 이 문제가 DFS인가?

: 이 문제가 DFS문제라는 것을 알고 푸니, 당연히 DFS라고 생각했지만 코딩테스트에는 DFS라고 명시해주지 않는다.

'섬'이라는 하나의 연결된 구조를 찾는 것이 목표인 문제다.

시작점(육지 셀)에서 '상, 하, 좌, 우' 더 이상 탐색할 수 없을 때까지 탐색하고 이전 분기점으로 돌아가 다른 경로를 탐색한다.

DFS는 이런 요구사항에 부합하는 알고리즘이다.

 

2) 왜 Scanner를 안쓰고 BufferedReader를 썼는가?

: Scanner는 사용하기 더 쉽지만 대용량 데이터 처리시 느릴 수 있다.

BufferedReader는 버퍼를 사용하여 일괄적으로 데이터를 읽기 때문에 대용량에서는 Scanner보다 효율적이다.

이 문제를 풀때, BufferedReader를 사용했다.

입력 데이터가 그렇게 대용량은 아니었지만, BufferedReader 사용법을 익히고 싶었다.

 

3) 생각회로

입력값을 어떻게 변수에 담아줄지 고민하기

➡️ 방문했던 경로를 재방문하지않으려면 visit배열을 만들어야하는지 안만들어도 되는지 고민해보기

➡️ 입력값을 순회하며 dfs를 호출하는 함수(countIslands)구현하기

➡️ dfs메서드 만들기

➡️ 값이 잘 들어가고 있는지 디버깅하기

 

package leetcode;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;

    public class NumberOfIslands {
        public static void main(String[] args) throws IOException {
            //BufferedReader는 Scanner에 비해 성능이 빠르다.
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

            String line = br.readLine(); // 전체 입력을 한줄로 받음.
            line = line.substring(1,line.length()-1); //양끝에 대괄호 제거함.
            String[] rows = line.split("\\],\\["); //],[을 기준으로 행을 구분한다.
            String[][] grid = new String[rows.length][]; // 행의 수에 맞게 그리드 초기화
            int row = 0; //행
            int col = 0; //열

            for(String rowData : rows){
                rowData = rowData.replace("\"",""); //쌍따옴표 제거
                String[] cols = rowData.split(","); //쉼표로 열 구분
                grid[row] = cols; // 행데이터를 그리드에 할당
                row++; //
            }
            int x = grid.length;//행의 수
            int y = grid[0].length; //열의 수

            int islandCount = countIslands(grid, x, y);//섬의 개수를 계산하는 메서드를 호출한다.

            bw.write(String.valueOf(islandCount)); //섬의 개수 출력
            //write메서드는 문자열을 인자로 받기때문에 int타입은 String으로 변환해줘야한다.
            bw.newLine(); //새 줄을 시작한다.

            br.close();//BufferedReader객체를 닫는다.
            bw.close();//BufferedWriter객체를 닫는다.
            //왜?
        }

        private static int countIslands(String[][] grid, int rows, int cols) {
            int count = 0;//섬의 개수를 세는 변수를 초기화한다.
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    if (grid[i][j].equals("1")) {//현재 위치가 '1'(육지)라면,
                        dfs(grid, i, j, rows, cols);//dfs를 실행시킨다.
                        count++; //섬의 개수를 증가시킨다. 1이 있으면 일단 무조건 섬은 최소 1개니까..! 바로 ++해줘버림
                    }
                }
            }
            return count; //반복문이 끝나면 계산된 섬의 총 개수가 나온다.
        }

        private static void dfs(String[][] grid, int i, int j, int rows, int cols) {
            if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j].equals("0")) {
                //i: 행 인덱스, j:열 인덱스
                //배열의 경계를 넘어가거나,물("0")을 만나면 return한다.
                return;
            }

            grid[i][j] = "0"; // 현재의 위치를 '0'으로 표시하여 방문했음을 나타낸다.

            //인접한 네 방향으로 dfs를 재귀호출한다.
            dfs(grid, i - 1, j, rows, cols);
            dfs(grid, i + 1, j, rows, cols);
            dfs(grid, i, j - 1, rows, cols);
            dfs(grid, i, j + 1, rows, cols);
        }
    }

 

3.  새롭게 알게된 점 

- DFS알고리즘 문제를 풀 때, visit배열을 따로 만들어주지 않아도 재방문 하지 않게끔 로직을 짤 수 있다.

- 문자열을 특정 구분자를 기준으로하여 토큰으로 분할 할때, 구분 문자열이 단순하면 StringTokenizer를 쓰지만 이번 문제처럼 복잡한 문자열 처리나 다중 구분자를 처리할 때는 split()을 쓰는게 낫다.

- 2차원 배열 그리드를 초기화 해줄 때, String [ ][ ] grid = new String[행길이][ ];

이렇게 행의 수만 맞춰서 초기화 해줘도 된다. 배열이 꼭 정방형은 아니기 때문이다! 

 

 

4. 느낀점

알고리즘도 어렵지만 입출력 처리하는게 너무 헷갈린다;;BufferedReader, BufferedWriter, StringTokenizer, Scanner등 입출력 처리하는 것을 연습해야겠다.유형은 정해져있어서 빈출 입력값으로 몇번 연습하면 될 것 같다.알고리즘 8문제 풀어야 되는데,, 1문제 분석하는 것만 굉장히 오래걸린다.그치만 반복하다보면 익숙해지겠지..