[프로그래머스] 무인도 여행

---

🔗 문제 링크

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

프로그래머스

---

반응형

728x90

👩‍💻 코드

#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>

using namespace std;

struct Position{
    int x;
    int y;
};

bool IsAllCheck(const vector<vector<bool>> &visited, const vector<string>& maps){
    for(int i=0; i<visited.size(); i++){
        for(int j=0; j<visited[i].size(); j++){
            if(!visited[i][j] && maps[i][j] != 'X'){
                return false;
            }
        }
    }
    
    return true;
}

vector<int> solution(vector<string> maps) {
    int row = maps.size();
    int column = maps[0].size();
    int dx[4] = {1,-1,0,0};
    int dy[4] = {0,0,1,-1};
    vector<int> answer;
    vector<vector<bool>> visited(row, vector<bool> (column, false));
    stack<Position> s;
    
    while(!IsAllCheck(visited, maps)){
        bool foundIsland = false;
        int sum = 0;
        
        for(int r=0; r<row; r++){
            for(int c=0; c<column; c++){
                if(maps[r][c] != 'X' && !visited[r][c]){
                    s.push({r, c});
                    sum += maps[r][c] - '0';
                    visited[r][c] = true;
                    foundIsland = true;

                    break;
                }
            }
            
            if(foundIsland){
                break;
            }
        }

        while(!s.empty()){
            Position p = s.top();
            s.pop();

            for(int i=0; i<4; i++){
                int x = p.x + dx[i];
                int y = p.y + dy[i];

                if(x >= 0 && x < row && y >= 0 && y < column && !visited[x][y] && maps[x][y] != 'X'){
                    visited[x][y] = true;
                    sum += maps[x][y] - '0';
                    s.push({x, y});
                }
            }
        }

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

---

📝 풀이

IsAllCheck 함수는 지도의 모든 무인도에 방문을 하였는지 확인하는 함수입니다.

 

지도의 (0,0)부터 방문하지 않은 무인도의 위치를 찾아 탐색을 시작합니다.

그 위치와 상,하,좌,우 인접한 무인도가 있는지 모두 찾습니다.

무인도를 찾을 때마다 식량의 값을 sum에 더합니다.

탐색을 시작한 무인도에 인접한 무인도를 모두 찾았으면 sum을 answer에 push 합니다.

이 과정을 지도의 모든 무인도를 방문할 때까지 반복합니다.

 

지도의 모든 무인도를 방문하고도 answer이 비어있다면 지낼 수 있는 무인도가 없으므로 {-1}를 return 합니다.

비어있지 않다면 answer을 오름차순으로 정렬한 후 return 합니다.