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

안녕하세요 ㅎㅎ

시작점을 다시 방문해서 그렇습니다.

이렇게 고쳐보시겠어요?

/*
육지 1, 바다 0
최단 거리 중 가장 먼 곳 => BFS & 테스트 케이스로 각 육지마다 순회
1. 방문 배열 초기화
2. 육지 찾기
3. BFS
4. 최단 거리 max update
*/
#include<bits/stdc++.h>
using namespace std;

int a[54][54];
int visited[54][54];
int n, m, res = 0;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
string s;
int BFS(int y, int x){
    queue<pair<int, int>> q;
    visited[y][x] = 1;
    q.push({y, x});
    int dis = 0;
    while(!q.empty()){
        tie(y, x) = q.front();
        q.pop();
        for(int i = 0; i < 4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
            if(visited[ny][nx] || a[ny][nx] == 0) continue;
            visited[ny][nx] = visited[y][x] + 1;
            //한 점에서의 최대 거리
            dis = max(dis, visited[ny][nx]);
            q.push({ny, nx});
        }
    }
    return dis;
}
int main(){
    cin >> n >> m;
    // int형으로 배열 생성
    for(int i = 0; i < n; i++){
        cin >> s;
        for(int j = 0; j < m; j++){
            if(s[j] == 'L') a[i][j] = 1;
            else a[i][j] = 0;
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(a[i][j] == 1){
                fill(&visited[0][0], &visited[0][0] + 54 * 54, 0);
                res = max(res, BFS(i, j));
            }
        }
    }
    cout << res - 1;
}

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

브리게이드98님, BFS를 활용하여 문제를 해결하는 과정에서 어려움을 겪고 계신 것 같습니다. BFS를 사용한 코드에서 특정 테스트 케이스는 통과했지만, 전체적으로 오답이라고 나오는 경우는 주로 다음의 요인에 의해 발생할 수 있습니다:

1. 초기화 문제: BFS를 여러 번 호출하는 경우 각 호출마다 필요한 배열이나 변수들이 제대로 초기화되지 않을 수 있습니다. 각 BFS 실행 전, 필수적인 배열들을 초기화했는지 확인해 보세요.

2. 경계 조건 처리: 특히 2차원 배열을 사용할 때 인덱스가 경계를 넘지 않는지, 시작 조건과 종료 조건이 올바르게 설정되어 있는지 확인해야 합니다.

3. 깊숙한 복사 문제: 연산이 오래 걸리거나 반복이 많은 배열의 경우, 깊은 복사 대신 얕은 복사가 이루어져 의도치 않은 값들이 남아 있을 수 있습니다.

기본적인 BFS 알고리즘과 관련한 내용은 인프런의 관련 질문 사례에서 비슷한 오류 해결 방법을 찾아보시면 도움이 될 수 있습니다. BFS의 전형적인 예시를 통해 초기화 및 경계 조건을 점검해 보는 것이 좋겠습니다.

추가적인 정보를 제공해 주시면 보다 구체적인 도움을 드릴 수 있습니다. BFS에 기반한 코드 작성에서 오류가 생기는 부분을 잘 점검해 보시길 바랍니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.