[Algorithm - DFS/BFS] BFS문제 풀기 ++ 응용(7576번, 1697번)

DFS/BFS의 가장 기본문제를 풀어보고 BOJ 1697번, 7576번에 적용해보도록 했다.

 

● 토마토(7576번)

 

미로찾기와 비슷한 유형의 문제인것같다. BFS를 적용하여 문제를 해결해야 하는 문제임은 알았지만,

(문제점 1) 1이 여러개 있을경우(시작지점이 여러개) 어떻게 적용해야할지 고민하고,

(문제점 2) 토마토가 모두 익을때까지의 최소 날짜 → BFS의 depth의 값을 알아야 했다.

 

예상외로 답은 간단했다.

문제점 1. 단순하게 처음부터 1의 시작점을 Queue에 넣게 되면 시작위치가 어디에 있던 queue.poll()을 했을때

자연스럽게 그곳에서 시작되는것이었다.

 

문제점 2. 하루가 지날때 익는 토마토의 값을 1이 아닌 처음 시작점의 1로부터 1씩 증가하도록 하고 마지막 하루를 빼주는 방식으로 계산하였다. 

static void BFS(int a, int b) {
        visited[a][b] = true;
        queue.add(new Point(a, b)); //Queue<Point> queue  = new LinkedList<Point>();

        while (!queue.isEmpty()) {
            Point point = queue.poll();
            a = point.x;
            b = point.y;

            for (int i = 0; i < 4; i++) {
                int x = a + dx[i];
                int y = b + dy[i];

                if (x >= 0 && y >= 0 && x < N && y < M) {
                    if (!visited[x][y] && arr[x][y] == 0) {
                        queue.add(new Point(x, y));
                        visited[x][y] = true;

                        arr[x][y] = arr[a][b]+1; // 이전값의 +1
                    }
                }
            }
        }

 

 

 

● 숨바꼭질(1697번)

위의 토마토 문제랑 큰 차이는 없는것 같다. 다만 여기서 메모리초과에 자꾸 걸렸다. 초기에 방문기록에 대한 check를 하지 않았는데 그래서 문제가 된것 같다.

 

static int BFS(int a, int b) {
        int[] arr = new int[100001]; // arr[a] = depth값 + arr!=0일 경우 방문확인
        queue.add(a);
        arr[a] = 1;

        while (!queue.isEmpty()) {
            a = queue.poll();

            for (int i = 0; i < 3; i++) {
                int x;
                if (i == 0) {
                    x = a + 1;
                } else if (i == 1) {
                    x = a - 1;

                } else {
                    x = a * 2;
                }
                if (x<=100000 && x>=0 && arr[x] == 0) {
                    queue.add(x);
                    arr[x]=arr[a]+1;
                    if (x == b) {
                        return arr[x]-1;
                    }
                }
            }

        }
        return 0;
        }

보면 정말 단순한데. 배열을 선언해서 depth값과 visited를 동시에 확인할 수 있다는것에 대해 알게되었다.

 

---

BFS와 DFS가 익숙해지면서 점점 눈에 보이는것 느낌이다.

BFS에서 queue를 넣고 .poll()을 하고 if문으로 조건문만 잘 설정하면 문제를 더 잘 해결 할 수 있을것 같다.