백준 11724번: 연결 요소의 개수

2020/12/08

문제

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

코드

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int[] nm = convertStringArrayToIntegerArray(br.readLine().split(" "));
    int n = nm[0];
    int m = nm[1];

    boolean[][] graph = new boolean[n+1][n+1];
    while (m-- > 0) {
        int[] xy = convertStringArrayToIntegerArray(br.readLine().split(" "));

        graph[xy[0]][xy[1]] = true;
        graph[xy[1]][xy[0]] = true;
    }

    int answer = 0;

    boolean[] isVisit = new boolean[n+1];
    for (int i = 1; i < graph.length; i++) {
        if (!isVisit[i]) {
            answer += bfs(isVisit, graph, i);
        }
    }

    System.out.println(answer);
}

private static int[] convertStringArrayToIntegerArray(String[] args) {
    int[] array = new int[args.length];
    int i = 0;
    for (String str : args) {
        array[i++] = Integer.parseInt(str);
    }

    return array;
}

private static int bfs(boolean[] isVisit, boolean[][] graph,int startIndex) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(startIndex);
    isVisit[startIndex] = true;

    while (!queue.isEmpty()) {
        int x = queue.poll();

        for (int i = 1; i < isVisit.length; i++) {
            if (isVisit[i]) {
                continue;
            }

            if (graph[x][i]) {
                queue.offer(i);
                isVisit[i] = true;
            }
        }
    }

    return 1;
}

흐름

그래프의 연결 관계를 인접행렬로 만들기 위해 정점의 개수 + n한 크기의 2차원 배열을 만들고,
이 문제에서 그래프는 방향이 없는 무방향 그래프이기 때문에 a->b로 가는 간선이 있으면 b->a로 가는 간선도 있는 것이므로 대칭이 되도록 배열에 저장한다.
이후 정점의 개수만큼 루프 돌면서 연결요소의 개수를 구하는데 아직 간선이 연결되지 않은 정점일 경우에만 BFS 탐색을 통해 탐색한다.
queue를 이용해 bfs를 구현하는데 우선 탐색이 시작되는 정점의 index를 queue에 저장하고, isVisit[] 변수에도 true로 해당 index를 탐색했다고 저장한다.
queue가 빌 때 까지 반복하면서 queue에 저장된 index를 poll한다.
정점의 개수 만큼 반복하면서 이미 연결된 정점이면 넘어가고
아직 연결되지 않은 정점이면서 다른 정점과 연결된 정점이면 queue에 해당 index를 저장하고, 방문했으니 true도 저장한다.
queue가 비어 루프가 종료되면 연결 요소 하나가 완성된 것이므로 1을 return 하고 bfs를 종료한다.
return된 1들을 저장해 모든 정점을 탐색 후 종료한다.
끝

결과

참고 사이트

https://sarah950716.tistory.com/12

댓글 공유

프로그래머스: 카카오 프렌즈 컬러링북

2020/06/11

문제

https://programmers.co.kr/learn/courses/30/lessons/1829

BFS(너비 우선 탐색) 알고리즘으로 해결

코드

public int[] solution(int m, int n, int[][] picture) {
    int numberOfArea = 0;
    int maxSizeOfOneArea = 0;

    boolean[][] isPassedArea = new boolean[m][n];

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {

            if (picture[i][j] == 0 || isPassedArea[i][j]) {
                continue;
            }

            int areaRange = breadthFirstSearch(i, j, picture, isPassedArea);
            maxSizeOfOneArea = (maxSizeOfOneArea < areaRange) ? areaRange : maxSizeOfOneArea;
            ++numberOfArea;
        }
    }

    int[] answer = new int[2];
    answer[0] = numberOfArea;
    answer[1] = maxSizeOfOneArea;

    return answer;
}

private int breadthFirstSearch(int x, int y, int[][] picture, boolean[][] isPassedArea) {
    final int[] xAround = new int[]{1, -1, 0, 0};
    final int[] yAround = new int[]{0, 0, 1, -1};

    int areaRange = 1;

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

    setPassedArea(isPassedArea, queue, x, y);

    while (!queue.isEmpty()) {
        Position currentPosition = queue.poll();

        for (int i = 0; i < xAround.length; i++) {
            int moveX = xAround[i] + currentPosition.x;
            int moveY = yAround[i] + currentPosition.y;

            if (!isSameAreaValidation(moveX, moveY, picture, isPassedArea, currentPosition)) {
                continue;
            }

            setPassedArea(isPassedArea, queue, moveX, moveY);
            ++areaRange;
        }
    }

    return areaRange;
}

private boolean isSameAreaValidation(int moveX, int moveY, int[][] picture, boolean[][] isPassedArea, Position currentPosition) {
    if (isOutOfPicture(moveX, moveY, picture)) {
        return false;
    }

    if (picture[moveX][moveY] == 0) {
        return false;
    }

    if (isPassedArea[moveX][moveY]) {
        return false;
    }

    if (picture[currentPosition.x][currentPosition.y] != picture[moveX][moveY]) {
        return false;
    }

    return true;
}

private boolean isOutOfPicture(int moveX, int moveY, int[][] picture) {
    if (moveX < 0 || moveY < 0) {
        return true;
    }

    if (picture.length <= moveX || picture[0].length <= moveY) {
        return true;
    }

    return false;
}

private void setPassedArea(boolean[][] isPassedArea, Queue<Position> queue, int x, int y) {
    isPassedArea[x][y] = true;
    queue.offer(new Position(x, y));
}

class Position {
    private int x = 0;
    private int y = 0;

    public Position(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

흐름

이미 지나온 배열인지 확인하기 위해 picture array와 똑같은 크기의 boolean array를 만듦
2차원 배열 크기만큼 돌면서 picture[i][j] value가 0이거나 이미 지나온 길이면 찾아갈 필요가 없으므로 continute 해서 길을 찾지 않음
아니면 좌표 x,y를 저장할 class를 담는 Queue를 생성함
queue에 현재 좌표를 저장하고 boolean array[x][y]를 true로 할당
queue에 있는 값을 하나씩 꺼내면서 queue가 전부 비워질 때까지 반복
queue에서 꺼낸 현재 좌표에서 상하 좌우를 비교해서 같은지 판단해야 하므로 현재 좌표에서 x -1 , +1, y +1, -1 씩 돌아가면서 판단할 좌표를 구함
구한 좌표가 validation을 통과하면 4번과 마찬가지로 좌표를 queue에 저장하고 true로 변경
1. 구한 좌표 x, y가 array 범위를 넘어가진 않는 지
2. 구한 좌표의 value가 0이 아닌 값 인지
3. 구한 좌표가 이미 지나간 길이 아닌지
4. 구한 좌표의 value가 현재 좌표의 value와 같은 지
5. 위 4가지를 모두 통과해야 validation 통과
현재 영역의 크기를 증가시킴
queue가 전부 비워지면 영역의 크기를 return해서 이전에 구한 영역의 크기와 비교해서 큰 값을 저장
영역 개수를 증가시킴
끝

결과

테스트 케이스

int[][] picture = new int[][] {{1, 1, 1, 0}, {1, 2, 2, 0}, {1, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 3}, {0, 0, 0, 3}};
assertArrayEquals(new int[] {4 , 5}, test.solution(6, 4, picture));

int[][] picture1 = new int[][] {{0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}};
assertArrayEquals(new int[] {0 , 0}, test.solution(5, 5, picture1));

int[][] picture2 = new int[][] {{1, 0, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 1}};
assertArrayEquals(new int[] {3 , 1}, test.solution(5, 5, picture2));

int[][] picture3 = new int[][] {{1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}};
assertArrayEquals(new int[] {1 , 25}, test.solution(5, 5, picture3));

int[][] picture4 = new int[][] {{1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 100, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}};
assertArrayEquals(new int[] {2 , 24}, test.solution(5, 5, picture4));

int[][] picture5 = new int[][] {{1, 1, 1, 0}, {1, 1, 1, 0}, {0, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 1}};
assertArrayEquals(new int[] {2 , 6}, test.solution(6, 4, picture5));

int[][] picture6 = new int[][] {{0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0}, {0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0}, {0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0}, {0, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 0}, {0, 1, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 1, 0}, {0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0}, {0, 1, 3, 3, 3, 1, 1, 1, 1, 1, 1, 3, 3, 3, 1, 0}, {0, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 0}, {0, 0, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 0, 0}, {0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0}, {0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0}};
assertArrayEquals(new int[] {12 , 120}, test.solution(13, 16, picture6));

참고 사이트

댓글 공유

백준 11724번: 연결 요소의 개수

문제

코드

흐름

결과

참고 사이트

프로그래머스: 카카오 프렌즈 컬러링북

문제

코드

흐름

결과

테스트 케이스

참고 사이트

Junggu Ji