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

문제: 

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

프로그래머스

 

풀이: 

 BFS 기본문제... 이어져있는 노드의 수를 모두 더해 answer에 추가해주는 방식으로 풀 수 있었다. 

 

코드 : 

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define X first
#define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1}; // 상하좌우 네 방향을 의미
bool visit[102][102];

vector<int> solution(vector<string> maps) {
    vector<int> answer;

    int n = maps.size();
    int m = maps[0].size();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(!visit[i][j] && maps[i][j]!='X')
            {
                queue <pair<int,int>> q;
                int cnt = maps[i][j] - '0';
                visit[i][j] = 1;
                q.push({i,j});
                while(!q.empty()){
                    pair <int, int> cur = q.front();
                    q.pop();
                    for(int dir = 0; dir < 4; dir++){
                        int nx = cur.X + dx[dir];
                        int ny = cur.Y + dy[dir];
                        if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                        if(visit[nx][ny]||maps[nx][ny]=='X') continue;
                        q.push({nx,ny});
                        cnt +=  maps[nx][ny] - '0';
                        visit[nx][ny] = 1;
                    }

                }
                answer.push_back(cnt);
            }
        }
    }

    if(answer.empty())
        answer.push_back(-1);
    sort(answer.begin(), answer.end());
    return answer;
}