[C++] 프로그래머스 Lv2. 무인도 여행

문제 링크

• https://school.programmers.co.kr/learn/courses/30/lessons/154540

풀이 방법

• 반복문을 통해서 maps를 순회한다.
• 순회하면서 숫자라면 BFS로 탐색한다.
• 상,하,좌,우를 탐색하면서 합을 구한다.
• 이미 방문을 했다면 넘어간다.

실패 풀이

• x,y의 초과범위를 잘못 설정하였다.
• maps가 n x n으로 설정된게 아니라 ny는 maps[i] 길이로 조건문을 둔다.

코드

bool vis[101][101];
const vector<pair<int, int>> delta{ {1,0} ,{-1,0} ,{0,1} ,{0,-1} };


vector<int> solution(vector<string> maps) {
    vector<int> answer;
    
    int size = maps.size();
    
    for(int i = 0;i<size;i++)
    {
        for(int j = 0;j<maps[i].size();j++)
        {
            if(!vis[i][j]&&isdigit(maps[i][j]))
            {
                int cnt = 0;
                queue<pair<int,int>> q;
                
                q.push({i,j});
                vis[i][j] = true;
                cnt+=(maps[i][j]-'0');
                
                while(!q.empty())
                {
                    auto cur = q.front();
                    q.pop();
                    
                    for(const auto& dir : delta)
                    {
                        int nx = dir.first + cur.first;
                        int ny = dir.second + cur.second;
                        
                        if (nx < 0 || nx >= size || ny < 0 || ny >= maps[i].size()) continue;
                        if(vis[nx][ny]) continue;
                        
                        if(isdigit(maps[nx][ny]))
                        {
                            q.push({nx,ny});
                            vis[nx][ny]  = true;
                            cnt += (maps[nx][ny]-'0');
                        }
                       
                    }
                }
                answer.push_back(cnt);
            }
        }
    }
    
    if(answer.empty()) return vector<int>{-1};
    sort(answer.begin(),answer.end());
    
    return answer;
}