lango

찍먹? 부먹?
난 부먹 개발자.

2 minute read



문제 풀이

이 문제는 그래프 탐색 알고리즘인 DFS나 BFS를 이용하면 쉽게 풀 수 있다. 필자는 BFS를 이용하여 풀었다.


아이디어 도출

주어지는 지도에서 연결된 섬인지를 알려면 이번 문제에서는 상,하,좌,우와 더불어 대각선으로 연결된 노드도 포함시켜서 탐색해야 한다. 대각선으로 탐색하는 것 외에는 연결된 노드의 개수를 구하면 되기에 크게 어렵진 않다.

1
2
3
4
5
6
7

// 상,하,좌,우 탐색하기 위한 dx, dy 배열
static int[] dx = new int[]{0, 1, 0, -1};
static int[] dy = new int[]{1, 0, -1, 0};

// 상하좌우와 대각선까지 탐색하기 위한 dx, dy 배열
static int[] dx = new int[]{0, 1, 0, -1, 1, -1, 1, -1};
static int[] dy = new int[]{1, 0, -1, 0, 1, 1, -1, -1};

위처럼 상,하,좌,우만 탐색하는 경우에 대각선 방향 4가지를 추가하여 탐색해야 한다.

그렇게 각 테스트케이스마다 주어지는 지도에서 섬(1)의 위치일 때마다 BFS로 탐색을 하고 BFS를 호출할 때마다 섬을 탐색하는 것이기에 카운트를 세면 BFS의 호출 횟수가 섬의 개수가 된다.


문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

import java.io.*;
import java.util.*;

class Main {    

    // 상하좌우와 대각선까지 탐색하기 위한 dx, dy 배열 선언
    static int[] dx = new int[]{0, 1, 0, -1, 1, -1, 1, -1};
    static int[] dy = new int[]{1, 0, -1, 0, 1, 1, -1, -1};

    // 방문 배열 선언
    static boolean[][] visited;

    // 지도의 크기 행 W, 높이 H 선언
    static int W;
    static int H;

    // 지도 배열 선언
    static int[][] map;

    // 섬의 개수를 담을 변수 선언
    static int cnt;

    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        // 0 0을 입력받을 때까지 순회
        while(true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            W = Integer.parseInt(st.nextToken());
            H = Integer.parseInt(st.nextToken());
            if(W == 0 && H == 0) break;

            // 지도 배열, 방문 배열, 섬의 개수 변수 초기화
            map = new int[H][W];
            visited = new boolean[H][W];
            cnt = 0;

            for(int i=0; i<H; i++) {
                st = new StringTokenizer(br.readLine());
                for(int j=0; j<W; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            
            // BFS 함수 호출될 때마다 카운트를 1 증가한다.
            // 결국, BFS 함수 호출 횟수가 섬의 개수가 된다.
            for(int i=0; i<H; i++) {
                for(int j=0; j<W; j++) {
                    if(map[i][j] == 1 && !visited[i][j]) {
                        cnt++;
                        BFS(i, j);
                    }
                }
            }
            sb.append(cnt+"\n");
        }

        bw.write(sb+"\n");

        bw.close();
        br.close();
    }

    static void BFS(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{x, y});
        visited[x][y] = true;
        while(!q.isEmpty()) {
            int[] now = q.poll();
            for(int dir=0; dir<8; dir++) {
                int i = now[0] + dx[dir];
                int j = now[1] + dy[dir];
                if(isRange(i, j)) {
                    if(map[i][j] == 1 && !visited[i][j]) {
                        visited[i][j] = true;
                        q.add(new int[]{i, j});
                    }
                }
            }
        }
    }

    static boolean isRange(int x, int y) {
        if(0<=x && 0<=y && x<H && y<W) {
            return true;
        }
        return false;
    }

}

출처

  • 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.

You may also enjoy