[백준] 섬의 개수 (BufferedReader, DFS, 좌표 ➡️ 2차원 배열, 4963번, Java)

 

문제설명

입력 & 출력

나의 풀이

---

먼저 이번 문제는 1 : 땅, 0 : 바다로 이루어진 지도가 주어졌을 때 섬의 개수를 구하는 문제입니다.

 

단 섬이 연결되어 있는 경우는 하나의 섬으로 간주하기 때문에 이 점을 고려해야합니다. 이동할 수 있는 방향은 가로,세로,대각선입니다. 

 

먼저 계속해서 호출되는 변수들을 가독성이 좋도록 전역변수로 선언합니다.

 

그리고 섬이 이동할 수 있으면 하나의 섬으로 간주하기 때문에 섬에서 다른 섬으로 이동할 수 있는 방향을 지정해줍니다.

(좌상단,우상단,좌하단,우하단,상,하,좌,우)

 

문제에서 가로,세로,대각선을 이동할 수 있다고 했기 때문에 위와 같이 이동 방향을 지정해줍니다.

 

이동방향에 대한 자세한 설명은 참고에 있는 포스트를 참고해주세요.

 

그리고 DFS함수를 선언해줍니다.

 

DFS함수에서는 먼저 인자로 받은 현재 위치를 방문처리 해주고, 현재 위치 x와 y를 전역 변수로 선언한 이동방향의 요소를 더해 다음 위치를 'nextX'와 'nextY'로 저장을 합니다.

 

x축은 실제로 세로로 이동하기 때문에 rows로 y축은 가로로 이동하기 때문에 cols로 범위 제한을 둡니다. 그리고 방문을 하지 않았고, 섬인 경우(1) dfs함수를 재귀 호출해줍니다.

 

 

main문에서는 빠른 입력을 위해서 BufferedReader클래스를 사용하여 입력을 받아주고, 각 좌표를 구분하기 위해 StringTokenizer를 사용했습니다.

 

그리고 "0 0"이 들어오지 않는다면 계속해서 입력을 받아야 하기 때문에 while문을 무한반복해줍니다.

 

41,42번째 줄에서 가로와 세로를 받는 데 이때도 좌표 ➡️배열 매핑이기 때문에 map[열][행]식으로 매핑을 해줘야합니다.

 

그리고 입력받은 가로 세로 만큼 배열을 초기화 해주고, 받은 정보를 지도에 저장을 해줍니다.

 

 

가로와 세로의 크기만큼 반복문을 돌려 지도의 모든 위치를 탐색합니다. 각 위치에서 인접한 섬을 찾는 조건을 만족하면 dfs 함수를 호출하여 탐색을 시작하고, 섬의 개수를 세어줍니다.

 

참고❗️

[JAVA] 입출력, BufferedReader, StringTokenizer, StringBuilder 알아보기

[JAVA] 좌표와 2차원 배열 매핑의 이해 (좌표 ➡️ 배열)