📌 문제 탐색하기
- 첫째 줄:
- W (지도의 너비, 최대 50)
- H (지도의 높이, 최대 50)
- 둘째 줄부터 지도 높이(H)만큼 이어서:
- 해당 지도에 섬이 존재하는지에 대한 정보
- 1: 땅
- 0: 바다
- 입력의 마지막 줄은 0 0으로 종료됩니다.
- 출력
- 각 지도에 대해, 상하좌우 및 대각선(8방향)으로 연결된 땅이 하나의 섬을 이루므로, 각 지도에서 섬의 개수를 출력해야 합니다.
📌 어떤 알고리즘?
- 그래프 탐색 알고리즘
- 주어진 문제에서 상하좌우 및 대각선으로 연결된 땅은 하나의 섬으로 간주합니다.
- DFS 또는 BFS를 활용하여 연결된 땅의 개수를 탐색하고, 이를 통해 섬의 개수를 구할 수 있습니다.
📌 코드 설계하기
- Input 받기 & 값 초기화
while (true) {
st = new StringTokenizer(bf.readLine(), " ");
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
if (w == 0 && h == 0) {
break;
}
int[][] map = new int[h][w];
boolean[][] visited = new boolean[h][w];
for (int i = 0; i < h; i++) {
st = new StringTokenizer(bf.readLine(), " ");
for (int j = 0; j < w; j++) {
while (st.hasMoreTokens()) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
}
- while 루프 안에서 너비(w)와 높이(h)를 입력받습니다.
- 0 0이 입력되면 반복을 종료합니다.
- 지도는 map이라는 2차원 배열로, 방문 여부는 visited라는 2차원 배열로 저장합니다.
- DFS를 이용한 섬 탐색
- 각 칸을 탐색하면서, 방문하지 않았고 땅(1)이면 DFS를 시작합니다.
public static int howManyIsLands(int[][] map, boolean[][] visited) {
int count = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (map[i][j] == 1 && !visited[i][j]) {
dfs(map, visited, i, j);
count++;
}
}
}
return count;
}
- DFS는 해당 칸과 연결된 모든 땅을 방문 처리하며, 섬의 개수를 count합니다.
public static void dfs(int[][] map, boolean[][] visited, int i, int j) {
stack.push(new int[]{i, j});
visited[i][j] = true;
while (!stack.isEmpty()) {
int[] current = stack.pop();
int dx = current[0];
int dy = current[1];
for (int k = 0; k < dX.length; k++) {
int x = dx + dX[k];
int y = dy + dY[k];
if (x >= 0 && y >= 0 && x < h && y < w && map[x][y] == 1 && !visited[x][y]) {
stack.push(new int[]{x, y});
visited[x][y] = true;
}
}
}
}
📌 시도 회차 수정 사항
- 초기 구현:
- 처음에 while 루프 내 st.hasMoreTokens()로 인해 여러 번 중복 입력을 받아 오류가 발생하였습니다.
- 해결:
- 중복 루프를 제거하고 for 루프 내에서 st.nextToken()을 호출하여 올바르게 데이터를 읽도록 수정하였습니다.
📌 정답 코드
package BOJ_4963;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class BOJ_4963 {
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static Stack<int[]> stack = new Stack<>();
static int[] dX = {0, 0, -1, 1, -1, -1, 1, 1};
static int[] dY = {1, -1, 0, 0, 1, -1, 1, -1};
static int w;
static int h;
public static void main(String[] args) throws IOException {
while (true) {
st = new StringTokenizer(bf.readLine(), " ");
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
if (w == 0 && h == 0) {
break;
}
int[][] map = new int[h][w];
boolean[][] visited = new boolean[h][w];
for (int i = 0; i < h; i++) {
st = new StringTokenizer(bf.readLine(), " ");
for (int j = 0; j < w; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
sb.append(howManyIsLands(map, visited)).append('\n');
}
System.out.println(sb);
}
public static int howManyIsLands(int[][] map, boolean[][] visited) {
int count = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (map[i][j] == 1 && !visited[i][j]) {
dfs(map, visited, i, j);
count++;
}
}
}
return count;
}
public static void dfs(int[][] map, boolean[][] visited, int i, int j) {
stack.push(new int[]{i, j});
visited[i][j] = true;
while (!stack.isEmpty()) {
int[] current = stack.pop();
int dx = current[0];
int dy = current[1];
for (int k = 0; k < dX.length; k++) {
int x = dx + dX[k];
int y = dy + dY[k];
if (x >= 0 && y >= 0 && x < h && y < w && map[x][y] == 1 && !visited[x][y]) {
stack.push(new int[]{x, y});
visited[x][y] = true;
}
}
}
}
}
📌 시간 복잡도?
- DFS의 시간 복잡도: O(H * W)
- 전체 지도를 한 번씩 순회하며, 방문하지 않은 땅에서 DFS를 호출하므로 H * W의 시간 복잡도를 가집니다.
- 공간 복잡도: O(H * W)
- 2차원 배열로 지도를 저장하며, 동일한 크기의 visited 배열을 사용합니다.
