문제 유형
n*n 크기의 2차원 배열이 주어졌을 때,
0은 바다 1은 섬을 의미한다.
섬은 상하좌우와 대각선으로 연결되어있다.
2차원 배열 내에서 섬 갯수를 구하시오
아래 그림의 섬 갯수는 5개이다.
필요 핵심 자료구조
int n // (2차원 배열 크기 변수),
int arr[][] // (n*n 크기의 2차원 배열),
int[] dx,dy // (상하좌우 배열),
int[] diaX, diaY // (대각선 배열),
Queue<SumnaraPoint> Q // (이동한 좌표를 담아줄 Queue),
BFS() 메서드 // 핵심 로직,
answer // 출력,
핵심 문제 해석
첫째 상하좌우 + 대각선으로 이어져있다는 점에 주목해야 한다.
대각선으로 이동한 좌표도 계산해야 하므로 대각선 배열을 만들어야 한다.
둘째 바다는 0이고, 섬은 1이다.
섬의 갯수를 구해야한다는 점에 주목해야
조건문을 작성할 때 수월하다.
문제 풀이 과정
섬의 갯수를 구하는 문제이므로,
arr의 좌표 값이 1일 때 BFS 로직을 실행하면 된다.
BFS 로직에서 한번 다녀간 arr 좌표는 1 -> 2로 변경해줘서
중복 로직 실행을 예방한다.
arr 좌표가 1에서 2로 변경되었기 때문에
BFS문을 호출할 때 불필요한 호출을 예방할 수 있게 된다.
그 이유는 아래 코드를 보면 이해할 수 있다.
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(arr[i][j] == 1) T.BFS(i, j);
}
}
arr 좌표 값이 1일 때 BFS를 호출하는데,
BFS 로직에서 이미 2로 초기화했기 때문에 불필요한 호출을 방지할 수 있게 된다.
상하좌우 또는 대각선으로 이동한 좌표 값을 Q에 담아주고,
그 값을 기준으로 인접한 섬으로 이동하면 되는 문제로 해석했기 때문에
BFS 알고리즘을 선택했다.
더 세부적으로 설명해보자면
상하좌우에 섬이 없다면 대각선도 함께 체크해서
이동할 수 있는 인접한 좌표가 존재한다면 모두 Queue에 담아주는
방식을 사용했기 때문에
DFS 방식보다는 BFS 방식이 더 적합하다고 생각했다.
인접한 섬이 없다면 Q가 Empty 상태가될 것이고
while문을 벗어나게 된다.
이말은 즉, 인접한 섬이 더이상 존재하지 않는다는 의미이고
섬의 갯수 한개를 모두 체크했다는 의미이므로
answer를 1 증가시켜줬다.
핵심 코드
public void BFS(int x, int y) {
if (arr[x][y] == 2) return;
Queue<SumnaraPoint> Q = new LinkedList<>();
Q.offer(new SumnaraPoint(x, y));
arr[x][y] = 2;
while (!Q.isEmpty()) {
int len = Q.size();
for(int i = 0; i < len; i++){
SumnaraPoint sP = Q.poll();
for (int j = 0; j < 4; j++) {
int nx = sP.x + dx[j];
int ny = sP.y + dy[j];
int nXD = sP.x + diaX[j]; // nextXDiagonal
int nYD = sP.y + diaY[j]; // nextYDiagonal
if (nx >= 0 && ny >= 0 && nx < n && ny < n && arr[nx][ny] == 1){
arr[nx][ny] = 2;
Q.offer(new SumnaraPoint(nx, ny));
}
if (nXD >= 0 && nYD >= 0 && nXD < n && nYD < n && arr[nXD][nYD] == 1){
arr[nXD][nYD] = 2;
Q.offer(new SumnaraPoint(nXD, nYD));
}
}
}
}
answer++;
}개선된 점
첫번째 자료구조와 응용 방법 생각해보기
문제에서 요구하는 조건인 대각선 이동을 어떻게 처리해줘야할지 그림으로 그려봤다.
처음에는 이차원 배열로 대각선 이동을 그려주고 코드를 작성했는데,
일차원 배열로도 처리해줄 수 있다는걸 깨달아서,
일차원 배열로 만들고 문제를 처리했다.
두번째 알고리즘 흐름 파악하기
DFS 또는 BFS 알고리즘을 그려가면서 어떤 알고리즘이 문제 해결에 더 적합할지 생각해봤다.
인접한 섬이 있는지 체크하는 문제이므로 BFS로 접근했다.
BFS 알고리즘을 그려보고 코드를 구현했다.
세번째 디버깅하기
문제를 다 풀어서 정답을 도출해냈을 때,
내 코드를 의심해보는 시간을 가져야한다.
실수한 부분은 없는지, 불필요한 변수는 없는지,
내부 동작이 내가 생각한대로 흘러가는지 .. 등을
디버깅으로 쉽고 명확하게 판단할 수 있다.
이번에도
디버깅을 통해 arr[x][y] = 2로 처리할 수 있었고,
내부 동작이 내가 생각한대로 흘러간다는걸 파악할 수 있었다.
피드백, 개선할 점
첫번째 문제풀이 속도 문제
처음 풀어보는 문제기 때문에 오래걸릴 수 있긴 하지만,
너무 느리다. (1시간 20분 정도 소요)
같은 유형의 문제를 만나면 금방 풀 수 있을 것 같다.
역시 많은 문제풀이 경험이 있을 수록 유리한 것 같다.
느낀점
첫번째 가장 중요한건 열심히보다 잘하는 것
내 문제점은 무엇일까,
어떤 부분이 약하고 개선해야할까
어떻게 하면 잘할 수 있을까?
라는 질문을 스스로에게 자주 던진다.
이런 생각을 하기 전과 하고 난 후에 알고리즘을 풀이하는 실력의
갭차이가 현저히 차이난다.
과거에는 문제가 주어지면 코드부터 구현한다던지,
에러가 발생하면 일일히 루프문을 생각해본다던지,
자료구조를 생각안하고 풀었고,
알고리즘 흐름도 생각하지 않았었다.
그저 감으로 문제를 풀었던 것이다.
하지만 잘하기 위해선 감이 아니라 논리적인 근거에 의거하여 풀이해야 한다.
그러기 위해선 자료구조 파악, 알고리즘 흐름 파악, 디버깅 ... 등을
시도하고 훈련해야 했다.
점점 익숙해져가고 있고,
실력이 많이 상승했음을 크게 느끼고 있음에 기쁘다.
