글 읽기 - java/ bfs 와 dfs 성능비교 (맞았는데 질문!)

sally3605 3년 전 0

제가 해당 문제를 dfs로 풀었을 때에는 360ms 정도에 통과했고,

bfs로 풀 때에는 528ms 로 통과를 해서 질문 드립니다!

사실 전 bfs가 더 효율적이고 빠르게 풀리는 문제라 생각했는데, dfs가 최적인 문제라면 문제의 어떤 부분을 힌트삼을 수 있는지 알고 싶습니다 !

아래의 코드는 제가 짠 bfs 코드입니다 감사합니다 :D

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static class RC{
        int row;
        int col;
        RC(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }

    static boolean isUnion;
    static int N, L, R;
    static int[][] world;
    static boolean[][] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = stoi(st.nextToken());
        L = stoi(st.nextToken());
        R = stoi(st.nextToken());
        world = new int[100][100];
        for (int i = 0; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N ; j++) {
                world[i][j] = stoi(st.nextToken());
            }
        }
        int day = 0;
        isUnion = true;
        while (isUnion) {
            isUnion = false;
            visit = new boolean[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visit[i][j])
                        bfs(i, j);
                }
            }
            if (isUnion)
                day++;
        }
        System.out.println(day);
    }

    static int[] dr = {0, 0, -1, 1};
    static int[] dc = {-1, 1, 0, 0};
    static Queue<RC> queue = new LinkedList<>();
    static List<RC> union = new ArrayList<>();

    static void bfs(int row, int col) {
        queue.clear();
        union.clear();
        int unionSum = 0;
        queue.add(new RC(row, col));
        union.add(new RC(row, col));
        visit[row][col] = true;

        while (!queue.isEmpty()) {
            RC tempRC = queue.poll();
            unionSum += world[tempRC.row][tempRC.col];

            for (int i = 0; i < 4 ; i++) {
                int nr = tempRC.row + dr[i];
                int nc = tempRC.col + dc[i];

                if (0 > nr || nr >= N || 0 > nc || nc >= N) continue;
                int people = Math.abs(world[tempRC.row][tempRC.col] - world[nr][nc]);
                if (L > people || people > R || visit[nr][nc]) continue;

                visit[nr][nc] = true;
                isUnion = true;
                queue.add(new RC(nr, nc));
                union.add(new RC(nr, nc));
//                System.out.println("adding " + nr +  " , " + nc);
            }
        }
        if (union.size() != 0)
            redistribute(unionSum);
    }

    static void redistribute(int unionSum) {
        int uSize = union.size();
        int avg = unionSum/uSize;

        for (int i = 0; i < uSize ; i++) {
            world[union.get(i).row][union.get(i).col] = avg;
        }
    }

    static int stoi(String str) {
        return Integer.parseInt(str);
    }
}

slah007 3년 전 1

BFS와 DFS는 탐색 방식이 달라 어느 것이 효율적임을 따질수는 없습니다. 개인적으로, DFS는 어떻게든 찾기만 하면 될 때 쓰고 BFS는 탐색 시 이동 횟수가 최소인 것을 찾을 때 쓰는 느낌입니다.

만약 둘 다 적용할 수 있는 문제가 있다면 선형 시간 내에 해결되도록 짜여있을테니 뭘 써도 상관없지만 저는 DFS를 권장합니다. 일단 DFS가 짜기 편하기도 하고, BFS는 queue에서 넣고 꺼내고 복사하는 과정을 거치는데 DFS의 함수 호출보다는 약간 느리고 메모리도 더 필요로 합니다.

sally3605 3년 전 0

@slah007 넵, dfs는 깊이우선 bfs는 너비우선이죠!

말씀대로 dfs함수보다 bfs가 메모리와 시간이 더 필요로 하네요, 저도 dfs 를 사용해야겠습니다 ㅎㅎ, 피드백 감사합니다 ! :)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

java/ bfs 와 dfs 성능비교 (맞았는데 질문!)

sally3605 3년 전 0

slah007 3년 전 1

sally3605 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말