문제 154540. 무인도 여행

문제 링크

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

프로그래머스

 

 

난이도 : Lv.2 

 

문제 요약 설명

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

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

 

입출력 예

입력

• 지도를 나타내는 문자열 배열 maps

입력 제한

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

입력 예제

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

// ans
[1, 1, 27]

 

풀이 방식

이 문제는 전형적인 BFS문제이다. dx, dy테크닉을 사용하여 격자 이동을 하고, 방문 여부를 저장하여, 중복된 위치를 방문하지 않도록 2차원 배열을 추가로 만들어 관리한다. 이러한 방식으로 모든 2차원 배열의 공간을 방문하여, 배열에 저장한 다음 오름차순 정렬을 하면 정답이 나온다.

 

정답 코드 

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

#define DIR 4

using namespace std;

int dx[DIR] = {1, 0, -1, 0};
int dy[DIR] = {0, 1, 0, -1};
int maps_r;
int maps_c;

vector<vector<bool>> visited;
vector<string> maps_global;

struct pos_data{
    int x;
    int y;
};

bool inRange(int x, int y){
    return 0 <= x && x < maps_r && 0 <= y && y < maps_c;
}

int bfs(int x, int y){
    int ans = 0;
    queue<pos_data> q;
    q.push({x, y});
    visited[x][y] = true;
    ans += maps_global[x][y] - '0';
    
    while(!q.empty()){
        pos_data cur_pos = q.front(); q.pop();
        
        for(int i = 0; i < DIR; i++){
            int nx = dx[i] + cur_pos.x;
            int ny = dy[i] + cur_pos.y;
            
            if(inRange(nx, ny) && !visited[nx][ny] && maps_global[nx][ny] != 'X'){
                q.push({nx, ny});
                visited[nx][ny] = true;
                ans += maps_global[nx][ny] - '0';
            }
        }
    }
    
    return ans;
}

vector<int> solution(vector<string> maps) {
    vector<int> answer;
    visited.resize(maps.size(), vector<bool>(maps[0].length()));
    swap(maps_global, maps);
    
    maps_r = maps_global.size();
    maps_c = maps_global[0].length();
        
    for(int i = 0; i < maps_r; i++){
        for(int j = 0; j < maps_c; j++){
            if(maps_global[i][j] != 'X' && !visited[i][j]){
                int ans = bfs(i, j);
                if(ans != 0){
                    answer.push_back(ans);
                }
                
            }
        }
    }
    
    // for(int i = 0; i < maps_r; i++){
    //     for(int j = 0; j < maps_c; j++){
    //         cout << visited[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
    
    if(answer.size() == 0){
        answer = {-1};
    }
    else{
        sort(answer.begin(), answer.end());
    }
    
    
    return answer;
}