85강,86강 섬나라 아일랜드(BFS,DFS)

알고리즘/자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

85강,86강 섬나라 아일랜드(BFS,DFS)

보름달빵 2025. 6. 27. 15:18

문제

N*N 크기의 섬나라 아일랜드 지도가 격자판의 정보로 주어진다. 각 섬은 1로 표시되어 상하좌우,대각선으로 연결되어 있으며 0은 바다다. 섬나라 아일랜드에 몇개의 섬이 있는지 구하여라.

입력 설명

첫 번째 줄에 자연수 N(3≤N≤20) 이 주어진다.

두번째줄 부터 격자판의 정보가 주어진다.

출력 설명

첫번째 줄에 섬의 개수를 출력한다.

입력 예제

7
1 1 0 0 0 1 0
0 1 1 0 1 1 0
0 1 0 0 0 0 0
0 0 0 1 0 1 1
1 1 0 1 1 0 0
1 0 0 0 1 0 0
1 0 1 0 1 0 0

출력 예제

문제 풀이

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

문제를 읽었을때 기존의 미로 문제와 달랐던 점은 "대각선" 이라고 생각했다. 특정한 지점에서 상하좌우를 확인할 때 dx,dy 배열을 만들어서 배열의 인덱스 값을 바꿨다면 이 문제는 대각선 4군데를 추가로 넣어줘야겠다고 생각했다.

arr[i][j] 가 현재 위치라고 할때, 상하좌우 그리고 1~4로 표시된 대각선의 값을 확인 할 수 있도록 dx,dy 배열의 값을 설정해주자.

static int n; // 섬의 크기
static int count=0; // 섬나라의 개수
static int[][] arr; // 섬의 정보
static boolean [][] visitied; // 방문 배열

그리고 위와 같이 나머지 필요한 static 변수들을 선언해주었다.

Main 코드

 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st;

    n = Integer.parseInt(br.readLine()); // N의 크기
    arr = new int[n][n];
    visitied = new boolean[n][n];

    // 배열의 정보 초기화
    for(int i=0;i<n;i++){
        st = new StringTokenizer(br.readLine());
        for(int j=0;j<n;j++){
            arr[i][j] = Integer.parseInt(st.nextToken());
        }
    }
    System.out.println(bfs());
}

Main 코드의 경우, 배열의 크기와 정보를 입력받고 섬나라의 개수를 구하는 bfs 코드를 호출해주는 것으로 하였다.

BFS,DFS 코드 설명

- bfs

처음에 배열의 값이 1인 노드들을 큐에 넣고 하나씩 노드들을 꺼내면서, 아직 방문하지 않았다면 해당 노드에서 bfs를 수행한다.
이후 내부에 있는 큐(node_queue)가 모두 비게 된다면 시작점인 된 노드에서 연결되어있는 모든 부분의 탐색이 완료된 것 이므로 섬의 개수를 저장하는 변수인 count의 값을 증가시켜준다.
이후에 다시 외부에 있는 큐(queue)로 돌아가서 배열의 값이 1인 노드를 꺼내는데, 만약 이미 방문처리가 되어있다면 해당 노드를 탐색하지 않고 다음 노드로 넘어간다.

-dfs

처음에 배열의 값이 1인 노드들을 큐에 넣고 하나씩 노드들을 꺼내면서, 아직 방문하지 않았다면 해당 노드에서 dfs를 수행한다.

Queue<Node> queue = new LinkedList<>();

// 배열을 탐색하며 1인 값을 큐에 넣기(시작점)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (arr[i][j] == 1) queue.add(new Node(i, j));
    }
}

위의 코드를 실행하고 나면, queue에는 (0,0),(0,1),(0,5),(1,1),(1,2).......(6,4) 의 노드들이 들어가 있을 것이다.

while (!queue.isEmpty()) { // 배열의 값이 1인 노드들을 모두 탐색
    Node curr = queue.poll();
    if (!visitied[curr.x][curr.y]) { // 베열의 값=1 && 아직 방문하지 않은 노드인 경우

그럼 큐에서 노드들을 하나씩 뽑으면서 해당 노드를 방문했는지 확인하기 때문에, 가장 먼저 (0,0) 노드가 뽑혀서 if 아래 문장이 실행 된다.
if 문 아래 부분에서 해당 노드와 연결된 지점들을 탐색할때 BFS로 탐색할지, DFS로 탐색할지에 따라 코드가 달라진다.

BFS

if (!visitied[curr.x][curr.y]) { // 베열의 값=1 && 아직 방문하지 않은 노드인 경우

    // 해당 노드에서 bfs 수행하기
    Queue<Node> node_queue = new LinkedList<>();

    visitied[curr.x][curr.y]=true;
    // 시작점 넣기
    node_queue.add(new Node(curr.x, curr.y));

    while(!node_queue.isEmpty()){
        Node node_curr = node_queue.poll();
        for(int i=0;i<8;i++){
            int nx= node_curr.x+dx[i];
            int ny= node_curr.y+dy[i];
            if(nx>=0&&nx<n && ny>=0 && ny<n && !visitied[nx][ny] && arr[nx][ny]==1){ // 범위에 맞는지는 반드시 확인!
                visitied[nx][ny]=true;
                node_queue.add(new Node(nx, ny));
            }
        }

    }
    count++;
}

(0,0) 노드를 방문처리하고, 새로운 큐인 node_queue에 넣는다.
node_queue에는 (0,0)이 존재하기 때문에 해당 노드를 뽑아서, 노드를 기준으로 8군데를 탐색하며 bfs를 수행하게 된다.
node_queue가 비게 된다는 것은 처음 노드를 시작으로 조건에 맞게 갈 수 있는 곳을 모두 탐색하였다는 뜻이기 때문에 하나의 섬이 완성된다. 따라서 count의 값을 증가시켜준다.

DFS

if (!visitied[curr.x][curr.y]) { // 베열의 값=1 && 아직 방문하지 않은 노드인 경우
                // 해당 노드에서 dfs 수행하기
                visitied[curr.x][curr.y]=true;
                dfs(curr.x,curr.y); 🚩
                count++; // 섬의 개수 세기
            }

static void dfs(int x,int y){
        for(int i=0;i<8;i++){
                int nx= x+ dx[i];
                int ny= y+ dy[i];
                if(nx>=0&&nx<n && ny>=0 && ny<n && !visitied[nx][ny] && arr[nx][ny]==1){
                    visitied[nx][ny]=true;
                    dfs(nx,ny);
                }
        }

    }

dfs로 코드를 작성하면 dfs의 호출이 끝나고 깃발 부분으로 되돌아 왔다는건, 출발점과 연결된 모든 노드들을 탐색하고 왔다는 뜻이다. 따라서 dfs의 호출이 끝난 이후에 count의 값을 증가시켜준다.

오류 - 범위를 꼭 체크해줘야한다.

올바른 코드

if(nx>=0&&nx<n && ny>=0 && ny<n && !visitied[nx][ny] && arr[nx][ny]==1)

오류가 발생하는 코드

if(!visitied[nx][ny] && arr[nx][ny]==1)

이 코드에서 범위를 확인하는 하는 부분을 처음에 넣지 않았었는데 ArrayIndexOutOfBoundsException이 발생했다.

처음에는 nx,ny가 범위에 맞지 않는 값이 들어가게 되면 어차피 위의 조건은 만족하지 않아서 false 값이 되므로 굳이 넣어줄 필요가 없다고 생각했었다.

하지만 범위와 관련된 조건식을 넣어주지 않는다면 visitied와 arr 검사를 하기 전에 이미 호출할 수 없는 값이 들어가기 때문에 배열 참조시 오류가 발생한다. 따라서 계산된 인덱스의 값이 배열의 크기에 맞는지 확인해주는 조건을 꼭 넣도록 하자!!

전체코드

package 섹션8_DFS_BFS심화;

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Q13_섬나라아일랜드_BFS {

    static int n;
    static int count=0; // 섬나라의 개수
    static int[][] arr;
    static boolean [][] visitied;

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


    static int bfs() {

        Queue<Node> queue = new LinkedList<>();

        // 배열을 탐색하며 1인 값을 큐에 넣기(시작점)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i][j] == 1) queue.add(new Node(i, j));
            }
        }

        while (!queue.isEmpty()) { // 배열의 값이 1인 노드들을 모두 탐색
            Node curr = queue.poll();
            if (!visitied[curr.x][curr.y]) { // 베열의 값=1 && 아직 방문하지 않은 노드인 경우

                // 해당 노드에서 bfs 수행하기
                Queue<Node> node_queue = new LinkedList<>();

                visitied[curr.x][curr.y]=true;
                // 시작점 넣기
                node_queue.add(new Node(curr.x, curr.y));

                while(!node_queue.isEmpty()){
                    Node node_curr = node_queue.poll();
                    for(int i=0;i<8;i++){
                        int nx= node_curr.x+dx[i];
                        int ny= node_curr.y+dy[i];
                        if(nx>=0&&nx<n && ny>=0 && ny<n && !visitied[nx][ny] && arr[nx][ny]==1){ // 범위에 맞는지는 반드시 확인!
                            visitied[nx][ny]=true;
                            node_queue.add(new Node(nx, ny));
                        }
                    }

                }
                count++;
            }
        }
        return count;
    }

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine()); // N의 크기
        arr = new int[n][n];
        visitied = new boolean[n][n];

        // 배열의 정보 초기화
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<n;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        System.out.println(bfs());
    }

    static class Node{
        int x;
        int y;
        Node(int x,int y){
            this.x=x;
            this.y=y;
        }
    }
}

package 섹션8_DFS_BFS심화;


import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Q13_섬나라아일랜드_DFS {
    static int n;
    static int count=0; // 섬나라의 개수
    static int[][] arr;
    static boolean [][] visitied;

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


    static int island() {

        Queue<Node> queue = new LinkedList<>();

        // 배열을 탐색하며 1인 값을 큐에 넣기(시작점)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i][j] == 1) queue.add(new Node(i, j));
            }
        }

        while (!queue.isEmpty()) { // 배열의 값이 1인 노드들을 모두 탐색
            Node curr = queue.poll();
            if (!visitied[curr.x][curr.y]) { // 베열의 값=1 && 아직 방문하지 않은 노드인 경우
                // 해당 노드에서 dfs 수행하기
                visitied[curr.x][curr.y]=true;
                dfs(curr.x,curr.y);
                count++; // 섬의 개수 세기
            }
        }
        return count;
    }

    static void dfs(int x,int y){
        for(int i=0;i<8;i++){
                int nx= x+ dx[i];
                int ny= y+ dy[i];
                if(nx>=0&&nx<n && ny>=0 && ny<n && !visitied[nx][ny] && arr[nx][ny]==1){
                    visitied[nx][ny]=true;
                    dfs(nx,ny);
                }
        }

    }

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine()); // N의 크기
        arr = new int[n][n];
        visitied = new boolean[n][n];

        // 배열의 정보 초기화
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<n;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        System.out.println(island());
    }

    static class Node{
        int x;
        int y;
        Node(int x,int y){
            this.x=x;
            this.y=y;
        }
    }
}

'알고리즘 > 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비' 카테고리의 다른 글

87강 피자 배달 거리 (백준 15686_치킨 배달) (1)	2025.07.01
84강 토마토 (0)	2025.06.26
83강 미로의 최단 거리 통로 (4)	2025.06.21
82강 미로탐색 (2)	2025.06.21
메모이제이션 (0)	2025.05.10

현재글85강,86강 섬나라 아일랜드(BFS,DFS)

츈츈's Spring

오블완, 티스토리챌린지,

Today :
Yesterday :

일	월	화	수	목	금	토
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

츈츈's Spring