백준 2667번 단지번호붙이기

문제

나의 풀이

import java.util.*;

public class Main {
    static class Pair {
        int x;
        int y;
        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public static final int dx[] = { 0, 0, 1, -1 };
    public static final int dy[] = { 1, -1, 0, 0 };
    public static void dfs(int[][] a, int[][] group, int x, int y, int count, int n) {
        group[x][y] = count; // 단지 번호
        for(int k = 0; k < 4; k++) {
            int nx = x + dy[k];
            int ny = y + dy[k];
            if(nx >= 0 && nx < n && ny >= 0 && ny < n) {
                if(a[nx][ny] == 1 && group[nx][ny] == 0) { // 집이면서 방문하지 않은 경우
                    dfs(a, group, nx, ny, count, n); // 이웃하기 때문에 같은 단지임
                }
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        int a[][] = new int[n][n];
        for(int i = 0; i < n; i++) {
            String s = sc.nextLine();
            for(int j = 0; j < n; j++) {
                a[i][j] = s.charAt(j) - '0';
            }
        }
        
        int count = 0;
        int group[][] = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(a[i][j] == 1 && group[i][j] == 0) {
                    dfs(a, group, i, j, ++count, n); // 새로운 단지 번호 부여
                }
            }
        }
        
        int answer[] = new int[count];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(group[i][j] != 0) {
                    answer[group[i][j] - 1] += 1; // 단지내 집의 개수 증가
                }
            }
        }
        
        Arrays.sort(answer); 
        System.out.println(count);
        for(int i = 0; i < count; i++) {
            System.out.println(answer[i]);
        }
    }
}

dfs 탐색을 통해서 단지 개수를 구한 뒤 단지번호마다 개수를 answer 배열을 통해 저장시켜서 이를 출력해주면 된다.

결과

백준 4963번 섬의 개수

문제

나의 풀이

import java.util.*;

public class Main {
    static class Pair {
        int x;
        int y;
        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static final int[] dx = {0, 0, 1, -1, 1, 1, -1, -1};
    public static final int[] dy = {1, -1, 0, 0, 1, -1, 1, -1};
    public static void bfs(int[][] a, int[][] group, int x, int y, int count, int n, int m) {
        Queue<Pair> q = new LinkedList<Pair>();
        q.add(new Pair(x, y));
        group[x][y] = count;
        while(!q.isEmpty()) {
            Pair p = q.poll();
            x = p.x;
            y = p.y;
            for(int k = 0; k < 8; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if(0 <= nx && nx < n && 0 <= ny && ny < m) {
                    if(a[nx][ny] == 1 && group[nx][ny] == 0) {
                        q.add(new Pair(nx, ny));
                        group[nx][ny] = count;
                    }
                }
            }
        }
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        while(true) {
            int m = sc.nextInt();
            int n = sc.nextInt();
            if(n == 0 && m == 0) {
                break;
            }
            int[][] a = new int[n][m];
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    a[i][j] = sc.nextInt();
                }
            }

            int count = 0;
            int[][] group = new int[n][m];
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    if(a[i][j] == 1 && group[i][j] == 0) {
                        bfs(a, group, i, j, ++count, n, m);
                    }
                }
            }
            System.out.println(count);
        }
    }
}

단지번호붙이기와 유사하지만 8방향으로 탐색해야 한다는 점만 유의하면 된다. 여기서는 bfs 탐색을 이용하였다.

결과

백준 2178번 미로 탐색

문제

나의 풀이

import java.util.*;

public class Main {
    static class Pair {
        int x;
        int y;
        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static final int dx[] = {0, 0, 1, -1};
    public static final int dy[] = {1, -1, 0, 0};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int a[][] = new int[n][m];
        sc.nextLine();
        for(int i = 0; i < n; i++) {
            String s = sc.nextLine();
            for(int j = 0; j < m; j++) {
                a[i][j] = s.charAt(j) - '0';
            }
        }

        int dist[][] = new int[n][m];
        boolean check[][] = new boolean[n][m];
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(0, 0)); // 시작점
        check[0][0] = true;
        dist[0][0] = 1;
        while(!q.isEmpty()) {
            Pair p = q.poll();
            int x = p.x;
            int y = p.y;
            for(int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if(0 <= nx && nx < n && 0 <= ny && ny < m) {
                    if(check[nx][ny] == false && a[nx][ny] == 1) { // 길이면서 아직 방문하지 않은 경우
                        q.add(new Pair(nx, ny));
                        dist[nx][ny] = dist[x][y] + 1;
                        check[nx][ny] = true;
                    }
                }
            }
        }
        System.out.println(dist[n - 1][m - 1]); // 도착점의 거리
    }
}

미로 탐색 문제는 단계별로 진행되는 bfs를 사용해야 한다. (최단거리 문제는 bfs를 이용한다.)
dist 배열을 이용해서 거리를 계산한다. 다음 노드를 방문할 때 현재 노드의 거리에 +1을 해주면 된다.

결과