코딩테스트 -- 무인도 여행 - (프로그래머스 / C++)

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

문제!

---

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

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

---

요약하면 배열을 줄테니 섬을 찾아내고, 각 섬들이 얼마동안의 식량을 가지고 있는지를 출력하는 문제였습니다.

예제를 보면

["X591X","X1X5X","X231X", "1XXX1"]

 

이런식으로 3개의 섬이 있다고 생각하고 각 섬의 식량합을 answer에 저장해주기만 하면 되는문제!

 

처음에는 한줄씩 연살하여 연결된 다음줄의 땅에다 연결 연결 하려고 했는데...

위의 예 처럼 떨어졌다가 이어지는 섬을 어떻게 처리 할지 감이 안잡혀서 이번에도 완전탐색으로 풀어보았습니다!

 

이번의 경우에는 경로가 필요하지도 않고 최단거리도 아니기에 dfs bfs 구분은 없을것 같아요!

 

저는 bfs로 풀어보았습니다.

 

 

먼저 사용체크해줄 배열, queue 리스트, 그리고 방향 배열을 만들어 줍시다.

int use[101][101]={0};
queue<pair<int,int>>list;

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

 

 

다음은 한칸씩 섬을 탐색해 주면서 땅을 만나면 bfs탐색을 시작하도록 해줍시다.

for(int i=0;i<maps.size();i++){
        for(int j=0;j<maps[i].size();j++){
            if(maps[i][j]!='X' and use[i][j]==0){ // 섬 탐색 시작
                list.push({i,j});
                isl_sum=maps[i][j]-'0';
                use[i][j]=1;

 

일반적인 bfs 방법에서  다를게 없네요..

while(!list.empty()){
                    pair<int,int> list_fro=list.front();
                    list.pop();

                    for(int k=0;k<4;k++){
                        int ch_y=list_fro.first+dy[k];
                        int ch_x=list_fro.second+dx[k];

                        if(ch_y<0 or ch_y>=maps.size() or ch_x<0 or ch_x>=maps[i].size() or use[ch_y][ch_x]==1){
                            continue;
                        }
                        else{
                            if(maps[ch_y][ch_x]!='X'){
                                list.push({ch_y,ch_x});
                                use[ch_y][ch_x]=1;
                                isl_sum+=maps[ch_y][ch_x]-'0';
                            }
                        }
                    }

이런식으로 섬을 찾아 answer에 추가해주고 sort 해주면 끝!

 

복잡한 문제는 아니였던것 같네요!

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int use[101][101]={0};
queue<pair<int,int>>list;

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

//어케할까 붙여서 저장해? 밑으로 내려오면서 붙어있는지 확인해?  ㄴ 탐색 ㄱㄱ

vector<int> solution(vector<string> maps) {
    vector<int> answer;
    int isl_sum=0;
    for(int i=0;i<maps.size();i++){
        for(int j=0;j<maps[i].size();j++){
            if(maps[i][j]!='X' and use[i][j]==0){ // 섬 탐색 시작
                list.push({i,j});
                isl_sum=maps[i][j]-'0';
                use[i][j]=1;

                while(!list.empty()){
                    pair<int,int> list_fro=list.front();
                    list.pop();

                    for(int k=0;k<4;k++){
                        int ch_y=list_fro.first+dy[k];
                        int ch_x=list_fro.second+dx[k];

                        if(ch_y<0 or ch_y>=maps.size() or ch_x<0 or ch_x>=maps[i].size() or use[ch_y][ch_x]==1){
                            continue;
                        }
                        else{
                            if(maps[ch_y][ch_x]!='X'){
                                list.push({ch_y,ch_x});
                                use[ch_y][ch_x]=1;
                                isl_sum+=maps[ch_y][ch_x]-'0';
                            }
                        }
                    }
                }
                answer.push_back(isl_sum);
            }
        }
    }

    
    if(answer.size()==0){
        return {-1};
    }

    sort(answer.begin(),answer.end());


    return answer;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!