백준 11123번 - 양 한마리... 양 두마리...

황제연·2024년 8월 9일

11123 BFS 메모리초과 백준 브루트포스 알고리즘 양한마리... 양두마리...자바 트러블슈팅

알고리즘

목록 보기

60/169

문제 탐색하기

입력 자료 정리하기

T는 문제를 반복할 테스트케이스의 개수이다
H은 이후 들어올 문자들을 보관할 배열의 가로길이, W는 배열의 세로길이이다
이후 들어오는 문자들은 조건으로 사용된다. #은 탐색조건, .은 무시될 탐색조건이다

해결방법 추론

이전에 숫자판 점프에서 봤듯이 좌표평면이 나오면 다음 방법을 고민해볼 수 있다
(브루트포스, 그래프 완전탐색(DFS/BFS), dp)
일단 h와 w입력 최댓값이 100, 100이며 테스트 케이스역시 100이기 때문에 DP는 사용할 필요가 없다
이 문제의 핵심은 양이 있는 곳을 발견하면 그 지점을 시작으로 상하좌우에 양이 또 있는지 확인해나가는 것이다
따라서 이 문제는 그래프 완전탐색으로 해결할 수 있으며,
DFS와 BFS중 BFS를 선택하였다.
또한 영역의 개수를 구해야하므로, 그래프 탐색 시작지점을 브루트포스로 돌면서 선택하도록 브루트포스 방법도 선택하였다.
따라서 브루트포스 + BFS를 사용하면 이 문제를 충분히 해결할 수 있겠다고 생각하였다
시간초과는 발생하지 않을까? 한번 계산해보자

시간복잡도 계산

일단 테스트 케이스에서 최대 입력값인 100의 연산이 발생한다
이후 시작지점 선택에서 h x w만큼 연산이 발생하므로
최대 입력값을 생각했을 때 100 * 100의 연산이 발생한다
BFS탐색에서는 얼마만큼의 연산이 발생할까? 최악의 경우 h x w만큼의 연산이 발생한다
최악의 경우는 모든 좌표에 양이 있는 경우다. 이 경우 h x w만큼의 탐색을 해야한다
하지만 이렇게 탐색을 하는 경우 브루트포스는 한번만 bfs 탐색을 실행한다.
그렇기에 브루트포스와 BFS 탐색의 연산은 동일선상에 두어야하고
테스트케이스와 곱연산을 해주어야한다
따라서 시간복잡도는 O(T x h x w)이다.
100 x 100 x 100이므로 시간제한에 걸리지 않는다!
해당 문제는 브루트포스와 BFS를 활용하여 문제를 해결할 수 있다!

코드 설계하기

입력값 상태 관리하기

테스트케이스는 T라는 int타입의 변수에 넣고 h, w 역시 int 타입 변수에 보관한다
양과 풀의 위치는 char 타입의 2차원 배열에 저장해준다.
테스트케이스마다 h,w, char 타입의 2차원 배열이 초기화되도록 한다

브루트포스 설계

이중포문을 돌면서 bfs 함수를 실행해준다.
현재 y, x 좌표를 나타내는 j와 k를 bfs 함수에 인자로 넘겨준다

BFS 탐색 설계

상하좌우 탐색을 편리하게 하기 위해 dx, dy 배열을 선언하였다
BFS 탐색에 있어서 같은 장소를 다시 방문하지 않게 하기 위해 방문체크 배열을 선언하였다
방문체크 배열은 boolean 타입의 2차원 배열이다
일반적으로 사용하는 방법인 큐를 활용하였으며,
y축과 x축을 동시에 받기 위해 int형 배열을 큐의 타입으로 지정하였다
인수로 넘어온 첫 위치의 값을 큐에 넣고 방문체크를한다
큐가 빌때까지 큐의 값을 하나씩 꺼내 탐색한다
상하좌우 이동범위가 인덱스 범위 안에 있고,
미방문 상태이며, 양이 있다는 의미인 '#'가 있다면 해당 위치를 방문 체크하고 큐에 넣어준다

출력값 설계

이 문제에서 출력해야할 정답은 양의 무리 개수이다.
따라서 브루트포스 하면서 bfs 함수를 실행시킬때 조건을 하나 넣어주어야한다
3.방문을 하지 않았고, 현재 위치가 '#'이라는 조건일때만 bfs 함수를 실행시킨다
4.bfs 함수 실행이 종료되면 하나의 무리 만큼 방문 체크도 하고
파악도 했다는 의미이므로, 무리의 개수인 count 값을 증가시킨다
완성된 count를 출력하면 정답이 된다

정답 코드

(1회 시도 성공!)

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


public class Main {

    static char[][] arr;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static boolean[][] visited;
    static int count = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int h = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            arr = new char[h][w];
            visited = new boolean[h][w];
            for (int j = 0; j < h; j++) {
                char[] s = br.readLine().toCharArray();
                for (int k = 0; k < w; k++) {
                    arr[j][k] = s[k];
                }
            }
            count = 0;

            for (int j = 0; j < h; j++) {
                for (int k = 0; k < w; k++) {
                    if(!visited[j][k] && arr[j][k] == '#'){
                        bfs(h, w, j,k);
                        count++;
                    }
                }
            }

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

        }


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

    private static void bfs(int h, int w, int i, int j) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{i,j});
        visited[i][j] = true;
        while(!q.isEmpty()){
            int[] cur = q.poll();
            for (int k = 0; k < 4; k++) {
                int ny = cur[0] + dy[k];
                int nx = cur[1] + dx[k];
                if(ny >=0 && ny < h && nx >= 0 && nx < w
                        && !visited[ny][nx] && arr[ny][nx] == '#'){
                    visited[ny][nx] = true;
                    q.add(new int[]{ny, nx});
                }
            }
        }
    }

}

BFS 메모리 초과 이슈 트러블 슈팅

발생 문제

과거에 내가 처음 BFS를 공부했을 때 발생했던 문제이다.
BFS 탐색에서 메모리 초과 이슈가 발생했던 문제다.
보통 DFS가 재귀방식이기 때문에 메모리 초과 이슈가 발생하는데,
이상하게도 BFS에서 메모리 초과 이슈가 발생하는 것이었다!

원인

원인은 방문체크의 순서 때문이었다.

if(ny >=0 && ny < h && nx >= 0 && nx < w
                        && !visited[ny][nx] && arr[ny][nx] == '#'){
                    q.add(new int[]{ny, nx});
                }

위와 같이 큐에 넣을 때 방문체크를 하지 않고,

while(!q.isEmpty()){
            int[] cur = q.poll();
            isited[cur[0]][cur[1]] = true;
            for (int k = 0; k < 4; k++) {
                int ny = cur[0] + dy[k];
                int nx = cur[1] + dx[k];
                if(ny >=0 && ny < h && nx >= 0 && nx < w
                        && !visited[ny][nx] && arr[ny][nx] == '#'){
                    v
                    q.add(new int[]{ny, nx});
                }
            }
        }

큐에서 뽑았을 때 방문체크를 했기 때문에 발생하는 문제였다
3. 방문 체크 순서의 변경이 대체 어떤 영향을 주기 때문에 이렇게 결과가 다를까?
4. 바로 중복된 탐색 값이 누적되어 들어가기 때문이다

예시

아래 예시를 보면,
시작지점을 기준으로 상하좌우 탐색을 하며 큐에 차례대로 들어가는 것을 예상할 수 있다
다음 순서는 먼저 들어간 2번 자리의 상하좌우 값이 큐에 들어갈 것이다.
물론 이때 탐색한 1번은 들어가지 않는다!
문제는 다음 탐색에서 발생한다 이제 3번의 상하좌우 탐색을 하는데 7번 위치가 다시 들어가게 된다
방문체크를 큐에서 뽑을 때 하고 들어갈 때는 하지 않기 때문에,
큐에서 순서대로 뽑을 때 이렇게 중복으로 들어가는 문제가 발생하는 것이다
연쇄적으로 이 문제가 발생하게 된다면
큐에 많은 데이터가 쌓이게 되어 메모리 초과 이슈가 충분히 발생할 수 있다

해결

해결방법은 간단하다. 큐에서 뺄때가 아닌 큐에 넣을 때 방문체크를 하면 된다!

private static void bfs(int h, int w, int i, int j) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{i,j});
        visited[i][j] = true;
        while(!q.isEmpty()){
            int[] cur = q.poll();
            for (int k = 0; k < 4; k++) {
                int ny = cur[0] + dy[k];
                int nx = cur[1] + dx[k];
                if(ny >=0 && ny < h && nx >= 0 && nx < w
                        && !visited[ny][nx] && arr[ny][nx] == '#'){
                    visited[ny][nx] = true;
                    q.add(new int[]{ny, nx});
                }
            }
        }
    }