[Java] 4963번 : 섬의 개수

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

Java로 언어를 바꾸면서,,,,난이도가 두배로 올라가버렸다,,!

이건 일반적인 dfs 문제이다. 오늘 8방 탐색을 해보았기 때문에, 연습으로 백준에서 비슷한 문제를 풀어봤다.

상, 하, 좌, 우만 생각하는 것이 아닌, 대각선까지 생각해주면 되는 문제였다.

나머지는 일반적인 dfs 코드와 동일하다.

 

오늘을 기점으로, 알고리즘도 종종 올려볼까 한당!

 

1. 상, 하, 좌, 우, 상좌, 상우, 하좌, 하우

static int[] dy = {-1, 1, 0, 0, 1, 1, -1, -1};
static int[] dx = {0, 0, -1, 1, -1, 1, -1, 1};

 

2. DFS 함수

private static void dfs(int x, int y) {
    visited[x][y] = 1;

    for(int i=0;i<8;i++) {
        int ny = dy[i] + y;
        int nx = dx[i] + x;

        if(ny<0 || nx<0 || ny>=n || nx >=m) continue;

        if(visited[nx][ny]==0 && arr[nx][ny]==1) {
            dfs(nx, ny);
        }
    }
}

 

3. 입력 받기,,,입력 받는게 제일 어려웠음 이게 맞나

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;

 

버퍼로 받아야 시간이 짧아진다는 걸 보고, Scanner에서 바꿨당!

https://velog.io/@sphill9803/%EB%B0%B1%EC%A4%80-BOJJAVA-JAVA%EB%A5%BC-%EC%9D%B4%EC%9A%A9%ED%95%9C-%EC%9E%85%EB%A0%A5-%EB%B0%9B%EA%B8%B0.-feat.-Scanner%EC%99%80-BufferReader%EC%9D%98-%EC%B0%A8%EC%9D%B4%EC%A0%90

[백준 BOJ][JAVA] JAVA를 이용한 입력 받기. (feat. Scanner와 BufferReader의 차이점)

st = new StringTokenizer(br.readLine());

arr = new int[54][54];
visited = new int[54][54];

n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());

if(n==0 && m==0) break;

for(int i=0;i<m;i++) {
    st = new StringTokenizer(br.readLine()," ");
    for(int j=0;j<n;j++) {
        arr[i][j] = Integer.parseInt(st.nextToken());
    }
}

 

4. 전체 코드

import java.util.Scanner;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int n, m;
    static int[][] visited;
    static int[][] arr;

    static int[] dy = {-1, 1, 0, 0, 1, 1, -1, -1};
    static int[] dx = {0, 0, -1, 1, -1, 1, -1, 1};

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        while(true) {
            st = new StringTokenizer(br.readLine());

            arr = new int[54][54];
            visited = new int[54][54];

            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());

            if(n==0 && m==0) break;

            for(int i=0;i<m;i++) {
                st = new StringTokenizer(br.readLine()," ");
                for(int j=0;j<n;j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            int cnt=0;
            for(int i=0;i<m;i++) {
                for(int j=0;j<n;j++) {
                    if(visited[i][j]==0 && arr[i][j]==1) {
                        dfs(i, j);
                        cnt++;
                    }
                }
            }

            System.out.println(cnt);
        }

    }
    private static void dfs(int x, int y) {
        visited[x][y] = 1;

        for(int i=0;i<8;i++) {
            int ny = dy[i] + y;
            int nx = dx[i] + x;

            if(ny<0 || nx<0 || ny>=n || nx >=m) continue;

            if(visited[nx][ny]==0 && arr[nx][ny]==1) {
                dfs(nx, ny);
            }
        }
    }
}