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

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

프로그래머스

 

 

해결 방법

이전에 풀었던 석유 시추와 비슷한 문제인데, 다른 점이라 하면 칸마다 수치가 다르다는 점이다. 

석유시추 문제를 풀 땐

0 : 석유없음 1 : 미검사 상태 2 이상 : 덩어리 id 부여받음

으로 행렬을 수정하면서 재귀로 문제를 풀었었다.  비슷하게, 이번 문제에서는

0 : 섬 없음 1~9: 미검사 10이상 :섬id 부여받음 

으로 해결할 수 있다. 

 

 

석유시추 문제는 여기있다.

https://journal-devchop.tistory.com/75

[프로그래머스] Level 2. 석유 시추

 

검사가 되었는지 안되었는지는 vector<vector<int>> m 의 값으로 판단하므로, 초기 세팅이 필요하다.

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

using namespace std;

void check(vector<string>& map , vector<vector<int>>& m, int i , int j ,vector<int>& count, int num){
    if(i>=m.size() || i<0 || j>=m[i].size() || j<0 || m[i][j] <= 0 || m[i][j]>9) return;
    
    if(count.size() <= num) count.push_back(0);
    
    count[num] += map[i][j]-'0'; //더미 수를 더함.
    m[i][j] = num+10; //id는 10부터시작.
    
    check(map,m,i+1,j,count,num);  //아래검사
    check(map,m,i-1,j,count,num);  //위 검사
    check(map,m,i,j+1, count, num); //오른쪽 검사
    check(map,m,i,j-1, count, num); //왼쪽 검사
    
    
}
vector<int> solution(vector<string> maps) {
    
    vector<vector<int>> m(maps.size(),vector<int>(maps[0].size(),0));
    vector<int> count;
    
    //초기세팅. 섬이 없다면 0, 있다면 1~9 사이의 숫자로 세팅함.
    for(int i =0; i<maps.size(); i++){
        for(int j =0; j<maps[i].size(); j++){
            if(maps[i][j]  !='X') m[i][j] = maps[i][j]-'0';
        }
    }
    
    for(int i =0; i<maps.size(); i++){
        for(int j = 0; j<maps[i].size() ;j++){
            check(maps,m,i,j, count, count.size());
        }
    }
    
    if(count.empty()) count.push_back(-1);
    else sort(count.begin(), count.end());
    
    return count;
}

 

헷갈릴 수 있는 점은, count 의 인덱스와 m에 부여되는 섬의 id는 다르다는 점이다.

count 가 [1,5,3] 이 되어있다면 1번 섬은 1일, 2번 섬은 5일, 3번 섬은 3일 버틸 수 있다는 의미이다.

실제 1번 섬에 해당하는 칸들에는 1이 아니라 10이 들어있을 것이다 . 1번이라고 적었을 경우, 검증이 끝난건지 아닌지 판단할 수 없기 때문이다. 

 

마무리 하며

2차원 배열로 주지 않고 vector<string> 으로 인자를 받았지만, 당황할 필요가 없다! 비슷한 문제를 풀게 된 김에, 다른 방법으로 풀만한 방법이 있을까? 고민해봤는데, 역시 재귀가 제일 좋은것같다.