인프런 커뮤니티 질문&답변

안녕하세요 ㅎㅎ

문제를 한 가지 방법이 아닌 여러 방법으로 접근해보고 있는데요, BFS를 이용한 완전탐색으로 변형을 해보려고 하는데 쉽지가 않네요;; ㅎㅎ

>> 이문제는 BFS로 하기에는 까다롭습니다.

이 문제의 경우 모든 경우의 수를 탐색해야 하는 것이고

그럴 때는 보통

        if(visited[next] == 0){
            visited[next] = 1; 
            go(ny, nx, cnt + 1);
            visited[next] = 0;  
        } 

이런식의 코드가 일반적인데 이를 queue에 담아서 구현하는 BFS로는 어렵습니다만...

이렇게 구현할 수는 있습니다.

#include <bits/stdc++.h>
using namespace std;

int R, C, ret;
char a[21][21];
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};

struct State {
    int y, x, cnt;
    bitset<26> visited;
};

void bfs() {
    queue<State> q;
    State start = {0, 0, 1, 0};
    start.visited[a[0][0] - 'A'] = 1;
    q.push(start);
    
    while (!q.empty()) {
        State cur = q.front();
        q.pop();
        ret = max(ret, cur.cnt);
        
        for (int i = 0; i < 4; i++) {
            int ny = cur.y + dy[i], nx = cur.x + dx[i];
            if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
            int next = a[ny][nx] - 'A';
            
            if (!cur.visited[next]) {
                State nextState = {ny, nx, cur.cnt + 1, cur.visited};
                nextState.visited[next] = 1;
                q.push(nextState);
            }
        }
    }
}

int main() {
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> a[i][j];
        }
    }
    bfs();
    cout << ret << '\n';
    return 0;
}

하지만 다음과 같이 메모리초과가 뜨고 굳이 이 방법을 추천드리지 않습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다.

DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 모두 완전 탐색 기법으로 사용될 수 있음은 분명합니다. 두 탐색 기법은 모두 그래프의 모든 노드를 방문하는 방법이지만, 그 접근 방식에서 차이가 있습니다. DFS는 한 경로를 맨 끝까지 탐색한 후 다른 경로를 탐색하는 반면, BFS는 시작점에서 가까운 노드부터 차례대로 탐색해 나갑니다.

DFS를 사용하여 문제를 해결한 경우, 일반적으로 재귀 함수를 통해 간단하게 구현할 수 있습니다. 그러나 BFS를 사용할 때는 Queue를 사용하여 구현하는 것이 일반적입니다. 이는 BFS가 동작하는 방식과 매우 밀접한 관련이 있습니다.

BFS를 이용한 완전탐색으로 접근하려 할 때 고려해야 하는 부분은 BFS가 각 노드를 방문할 때 도달 가능한 모든 경로를 거의 동시에 확장한다는 점입니다. 따라서, 기존 DFS를 통해 구현한 로직을 BFS로 변환하려면, 현재 노드에서 이동할 수 있는 모든 노드를 큐에 넣고, 이들 노드를 순차적으로 다시 탐색하는 방식으로 변경해야 합니다.

만약 이번 문제가 기존의 방식대로 BFS 변환에 어려움을 겪고 있다면, 문제의 특성을 다시 한번 살펴볼 필요가 있습니다. 문제의 구조, 요구하는 해결 방법 또는 최적화 조건 등을 고려하여 BFS가 유용하게 적용될 수 있는 방식을 찾아보시는 것이 좋습니다. BFS를 적용하려면 문제의 구조를 이해하고, 이를 어떻게 Queue로 관리하면서 단계별로 탐색할지 고민해보는 것이 중요합니다.

종종, 특정 문제에서는 BFS가 DFS보다 더 효율적인 해결 방법을 제공할 수 있습니다. 예를 들어, 최단 경로를 찾는 문제는 BFS를 사용해야 더 쉽게 접근할 수 있습니다. 따라서, 문제의 요구 사항과 조건을 철저히 분석한 후 적절한 탐색 기법을 선택하는 것이 중요합니다.

BFS를 적용하는 데 있어서 특별히 유의해야 할 점이나, 구현과 관련된 구체적인 도움이 필요하다면, 더 자세한 코드의 구조나 문제의 세부적인 내용을 공유해주시면 좋겠습니다.