프로그래머스 : 연습문제 > 무인도 여행(lv2) c++ BFS풀이

프로그래머스 링크

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

프로그래머스

문제 설명

메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다. 이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.

지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.

---

제한사항

• 3 ≤ maps의 길이 ≤ 100
  • 3 ≤ maps[i]의 길이 ≤ 100
  • maps[i]는 'X' 또는 1 과 9 사이의 자연수로 이루어진 문자열입니다.
  • 지도는 직사각형 형태입니다.

---

입출력 예mapsresult

["X591X","X1X5X","X231X", "1XXX1"]	[1, 1, 27]
["XXX","XXX","XXX"]	[-1]

---

입출력 예 설명

입출력 예 #1

위 문자열은 다음과 같은 지도를 나타냅니다.

연결된 땅들의 값을 합치면 다음과 같으며

이를 오름차순으로 정렬하면 [1, 1, 27]이 됩니다.

입출력 예 #2

위 문자열은 다음과 같은 지도를 나타냅니다.

섬이 존재하지 않기 때문에 -1을 배열에 담아 반환합니다.

코드 풀이

문제설명을 딱 읽으니깐 바로 BFS가 떠올라서 BFS로 풀이하였습니다.

1. 탐색할 방향을 정해주는 dx, dy 변수 지정
2. 방문했는지 판단하는 Visit 벡터와 위치를 저장할 queue Pair 생성
3. maps를 전부 탐색하기위한 2중 포문 지정 단 방문한 노드는 탐색하면 안 되니 시작 부분 예외처리 필수!
4.  q에 있는 값을 탐색하기 전 while문 밖에 머무르는 일 수를 저장할 변수 (AddRange라고 지정) 생성
   while문 밖에다가 변수를 생성한 이유는 while문이 끝났을 때는 하나의 인접한 구역을 전부 탐색 한 뒤이기 때문에
   for문을 돌았을 때는 새로운 구역이라는 의미이기 때문
5. 인접한 구역 탐색하면서 머무를 수 있는 날을 더해준다.
6. while문이 끝난 뒤 최종 머무르는 날을 answer에 더해줌
7. 마지막으로 for문이 전부 종료되었다면 모든 부분에 대한 탐색이 끝난 것이기 때문에 최종적으로 answer를 오름차순 정렬 시켜주었습니다.

코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

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

vector<int> solution(vector<string> maps) {
    vector<int> answer;
    
    
    int SizeX = maps[0].size();
    int SizeY = maps.size();
    
    // 방문했는지 판단하는 벡터
    vector<vector<bool>> Visit(SizeY, vector<bool>(SizeX, 0));
    
    // Position값을 저장하는 qpair
    queue<pair<int, int>> qPair;
    
    for(int i = 0; i < SizeY; ++i)
    {
        for(int j = 0; j < SizeX; ++j)
        {
            // 탐색x 예외처리
            if(maps[i][j] == 'X' || Visit[i][j] == true)
                continue;
            
            // 갈 수 있는 위치기 때문에 q에 위치 저장
            qPair.push({i, j});
            
            Visit[i][j] = true;
            int AddRange = 0;
            
            // 며칠 머물 수 있는지 숫자 +
            // while돌면서 인접한 위치를 전부 탐색하기 때문에
            // while 밖에다가 AddRange를 생성한것
            // 그러면 범위마다의 일수를 체크할 수 있다.
            AddRange += maps[i][j] - '0';
            
            while(!qPair.empty())
            {
                pair<int, int> Cur = qPair.front();
                
                qPair.pop();
                
                // 방향 탐색
                for(int Dir = 0; Dir < 4; ++Dir)
                {
                    // 다음 탐색 위치
                    int NextX = Cur.second + dx[Dir];
                    int NextY = Cur.first + dy[Dir];
                    
                    // 갈 수 없는지 판단 예외처리
                    if(NextX < 0 || NextY < 0 || NextX >= SizeX || NextY >= SizeY)
                        continue;
                    
                    if(maps[NextY][NextX] == 'X' || Visit[NextY][NextX] == 1)
                        continue;
                    
                    // 예외처리 지나왔으니 갈 수 있는 곳
                    qPair.push({NextY, NextX});
                    Visit[NextY][NextX] = true;
                    AddRange += maps[NextY][NextX] - '0';
                }
            }
            
            answer.push_back(AddRange);
        }
    }
    
    if(answer.size() == 0)
    {
        answer.push_back(-1);
        
        return answer;
    }
    
    sort(answer.begin(), answer.end());
    
    return answer;
}