3-B 질문

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

3-B

해결된 질문

작성

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

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

int n,m, visited[51][51], ret = 0;
char a[51][51];

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


void bfs(int y, int x){
    queue<pair<int,int>> q;
    memset(visited, 0, sizeof(visited));
    visited[y][x] = 1;
    q.push({y,x});
    int cnt = -1;
    while(q.size()){
        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 || nx < 0 || ny >= n || nx >= m || a[ny][nx] == 'W' || visited[ny][nx]) continue;
            visited[ny][nx] = visited[y][x] + 1;
            q.push({ny,nx});
            ret = max(ret, visited[ny][nx]);
        }
    }
    return;
}


int main(){
    cin >> n >> m;
    for(int i =0; i<n; i++){
        for(int j =0; j <m; j++){
            cin >> a[i][j];
        }
    }

    for(int i =0; i<n; i++){
        for(int j =0; j <m; j++){
            if(a[i][j] == 'L' && visited[i][j] == 0){
                bfs(i,j);
            }
        }
    }
  
    cout << ret-1 << "\n";
    return 0;
}

안녕하세요 선생님 제가 풀었던 문제인데
if(a[i][j] == 'L' && visited[i][j] == 0){ bfs(i,j); }

visited[i][j] == 0 이분분 때문에 자꾸 틀렸다고 나옵니다. 생각 해봐 없어서 되긴 하지만 있었도 문제가 없지 않나요?

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 창완님 ㅎㅎ

그렇게 하실 경우 memset 부분을 이동해야 합니다.

bfs가 끝나면 visited에 값이 생긴 정점이 있기 때문에 저렇게 하면 모든 정점을 탐색 못할 수도 있습니다.

참고로 창완님 코드처럼 하고 싶다면 다음과 같이 변경하시면 됩니다.

#include<bits/stdc++.h>
using namespace std; 
int n, m, mx, visited[54][54]; 
const int dy[] = {-1, 0, 1, 0}; 
const int dx[] = {0, 1, 0, -1}; 
char a[54][54];
void bfs(int y, int x){ 
    visited[y][x] = 1; 
    queue<pair<int, int>> q; 
    q.push({y, x}); 
    while(q.size()){
        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]) continue; 
            if(a[ny][nx] == 'W')continue;
            visited[ny][nx] = visited[y][x] + 1; 
            q.push({ny, nx});
            mx = max(mx, visited[ny][nx]);
        }
    }
    memset(visited, 0, sizeof(visited)); 
    return;
}
int main(){
    cin >> n >> m; 
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j]; 
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(a[i][j] == 'L' && visited[i][j] == 0) bfs(i, j); 
        }
    } 
    cout << mx - 1 << "\n";
}

감사합니다.

인프런 AI 인턴

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

안창완님, 여러분의 질문에 오신 것을 환영합니다. 작성해 주신 코드는 “L”인 모든 지점에서부터 BFS를 수행하여 최대 거리를 찾는 문제를 해결하려 하고 있습니다. visited[i][j] == 0 부분이 문제라고 생각되신 부분에 대해 설명드리겠습니다.

문제 이해

주어진 코드는 보물섬 문제와 유사한 형태로, 지도 상의 각 육지(“L”)에서 다른 모든 육지까지의 최장 거리를 탐색하려고 합니다. visited 배열은 이미 탐색된 지점을 다시 탐색하지 않기 위해 사용되는데, 각 BFS 탐색이 시작되기 전마다 memset으로 초기화되기 때문에, 해당 코드에서는 ‘L’을 발견할 때마다 BFS를 수행해도 됩니다.

`visited[i][j] == 0` 조건

코드에서 bfs(i, j)를 호출하기 전에 visited[i][j] == 0 조건이 필요하지 않을 수 있습니다. 이는 bfs 함수의 첫 동작으로 visited를 초기화하기 때문입니다. 따라서 visited 배열의 상태와 상관없이 ‘L’일 경우 BFS를 수행하도록 해도 됩니다.

컨셉 이해

BFS를 수행하며 최대 거리를 계산할 때 visited 배열은 내전적으로 탐색 깊이를 기록하여 탐색 효율성을 높이는 역할을 합니다. 이 때문에 각 ‘L’지점에서 새로운 BFS 탐색이 시작될 때, 이미 방문된 점은 무시할 수 있습니다.

정리

결론적으로, visited[i][j] == 0 조건은 memset 때문에 불필요합니다. ‘L’로 명시된 모든 지점을 대상으로 BFS를 수행하여 결과를 출력하는 것이 코드의 의도된 동작입니다. 이렇게 변경 후에도 문제가 지속될 경우, 입력 데이터의 형식이나 풀이 논리가 잘못되지 않았는지 확인해 보셔야 합니다.

관련 예제를 참조하시려면, BFS를 이용한 거리 계산과 관련된 인프런의 질문을 참고해 보세요.

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

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

3-B 질문

문제 이해

visited[i][j] == 0 조건

컨셉 이해

정리

`visited[i][j] == 0` 조건