[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문제 분석하는 것만 굉장히 오래걸린다.그치만 반복하다보면 익숙해지겠지..