글 읽기 - BFS의 코딩 스타일 문의

startlink 5년 전 0

다른 사람의 BFS 코드를 보다보면 제가 작성하는 것과 다른 스타일이 있는데, 이런 스타일은 어디서 배우는 것인가요?

혹시 이런 소스 스타일이 있는 책이나 인터넷 강의나 블로그 등을 찾습니다.

또는 제가 궁금해하는 스타일로 작성하는 이유가 있을까요? size는 제가 보기에는 불필요한 것으로 보입니다.

// 제 스타일
queue<int> q;
while (!q.empty()) {
    int x = q.front(); q.pop();
    for (int y: a[x]) {
        q.push(y);
    }
}
// 궁금한 스타일
queue<int> q;
while (!q.empty()) {
    int size = q.size();
    for (int i=0; i<size; i++) {
        int x = q.front(); q.pop();
        for (int y: a[x]) {
            q.push(y);
        }
    }
}
// 궁금하지만 이해할 수 있는 스타일
queue<int> q;
for (int step=1;; step++) {
    int size = q.size();
    for (int i=0; i<size; i++) {
        int x = q.front(); q.pop();
        for (int y: a[x]) {
            q.push(y);
        }
    }
}

시작 노드로 부터 몇 단계나 떨어져 있는 상태인지 쉽게 계산하기 위함인 듯 합니다.
2차원 grid에서 최단거리로 목표지점을 탐색해 나가는 경우를 예로 들어보면,
큐에 현재 위치정보 뿐만 아니라 시작지점부터 몇칸 이동한 상태인지도 나타내는 정보를 포함해야 하는데
메모리를 아끼기 위해 질문하신 코드에서처럼 q.size()를 이용하여 각 단계별로 큐에있는 정보를 분리시켜 준 것처럼 보입니다.

올리주신 코드에서는 단지 탐색하는 부분밖에 없어 차이가 없지만 말씀드린 예시의 상황에 유용할 것 같습니다.

gnues 5년 전 0

코드예시를 첨부해 보자면 이렇습니다.

int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};

// 2차원 위치(x,y), 시작지점부터 떨어진 거리
queue<tuple<int, int, int>> q;
while(!q.empty()) {
    int x, y, d;
    tie(x, y, d) = q.front(); q.pop();
    for(int dir=0; dir<4; dir++) {
        int nx = x + dx[dir], ny = y + dy[dir];
        if(/*condition*/) q.push({nx, ny, d+1});
    }
}

// 메모리를 절약하는 방식
queue<tuple<int, int>> q;
int d = 0;
while(!q.empty()) {
    int size = q.size();
    for(int i=0; i<size; i++) {
        int x, y;
        tie(x, y) = q.front(); q.pop();
        for(int dir=0; dir<4; dir++) {
            int nx = x + dx[dir], ny = y + dy[dir];
            if(/*condition*/) q.push({nx, ny});
        }
    }
    d++;
}

djm03178 5년 전 0

"궁금한 스타일"과 "궁금하지만 이해할 수 있는 스타일"이 결국 동일한 것이 아닌가요? "궁금한 스타일"에 step만 추가해서 루프가 끝날 때마다 하나씩 증가시키면 곧 "궁금하지만 이해할 수 있는 스타일"이 되겠네요.

startlink 5년 전 0

시작 노드로 부터 몇 단계나 떨어져 있는 상태인지는 저렇게 step을 나누지 않고도 구할 수 있는데, 그걸 왜 나누는지가 궁금한 것입니다. 어차피 BFS는 거리를 배열을 만들어서 계산하기 때문에, 별로 필요는 없어보이기 때문이지요.

"궁금한 스타일"과 "궁금하지만 이해할 수 있는 스타일"이 결국 동일한 것이 맞습니다. 그래도 이건 궁금한 스타일이지요.

많은 사람들이 저런 스타일을 구현하는데는 뭔가 출처라던가 어딘가 시작이 있을텐데, 그것이 궁금한 것입니다.

왜 저렇게 구현하는지 이해는 못하지만(제가 저런 방식이 효율적이라고 생각하지 않으니깐), 사용하는 이유는 저도 알고 있습니다.

startlink 5년 전 0

좀 더 의견을 추가하면, 모든 BFS를 저렇게 구현하는 분이 있어서 그렇습니다.

upple1 5년 전 1

저 방식대로 안하더라도 인트배열로 거리를 저장하면 최단거리를 구할 수 있지만 저 방식대로하면 bool배열로 방문체크만해서 거리구하는것이 가능해집니다. 속도면에선 모르겠지만 메모리면에서 1/4감소 효과가 있습니다.

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

문제

문제

출처

ICPC

BFS의 코딩 스타일 문의

startlink 5년 전 0

gnues 5년 전 0

gnues 5년 전 0

djm03178 5년 전 0

startlink 5년 전 0

startlink 5년 전 0

upple1 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말