[프로그래머스] Lv. 2 무인도 여행 (C++)

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

using namespace std;

// if the value of idx is 'X',
//     return.
// if the value of idx is not 'X',
//     add the number to foods.
//     mark the index as visited.
//     visit near islands.
bool visit(pair<int, int> idx, int& foods, vector<string>& maps, vector<vector<bool>>& visited) {
    int row = idx.first;
    int col = idx.second;

    if (visited[row][col])
        return false;
    else
        visited[row][col] = true;

    char value = maps[row][col];

    if (value == 'X')
        return false;
    else {
        foods += value - '0';
        // 상 (맨 위 행이 아닐 때만)
        if (row != 0) visit({row-1, col}, foods, maps, visited);
        // 하 (맨 아래 행이 아닐 때만)
        if (row != maps.size()-1) visit({row+1, col}, foods, maps, visited);
        // 좌 (맨 왼쪽 열이 아닐 때만)
        if (col != 0) visit({row, col-1}, foods, maps, visited);
        // 우 (맨 오른쪽 열이 아닐 때만)
        if (col != maps[0].size()-1) visit({row, col+1}, foods, maps, visited);
    }

    return true;
}

vector<int> solution(vector<string> maps) {
    // calculate the number of rows, columns
    int rows = (int)maps.size();
    int cols = (int)maps[0].size();

    // record wheather visited or not
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));

    vector<int> answer;
    int foods = 0;
    for (int i = 0; i < rows; i++)
        for (int j = 0; j < cols; j++) {
            foods = 0;
            if (!visited[i][j] && visit({i, j}, foods, maps, visited))
                answer.push_back(foods);
        }

    if (answer.size() == 0)
        answer.push_back(-1);
    else
        sort(answer.begin(), answer.end());
    return answer;
}

visit() 함수

---

함수 원형

bool visit(pair<int, int> idx, int& foods, vector<string>& maps, vector<vector<bool>>& visited)

 

visit() 함수는 특정 위치를 idx로 입력 받아, 그 위치를 방문한다. 만일 그 지점이 이전에 방문한 적이 있다면, 즉시 false를 반환한다. 방문한 적이 없다면, 그 지점의 값이 무엇인지 검사한다. 검사한 값이 'X'라면, 즉시 false를 반환한다. 값이 '0'에서 '9'라면, 그 값을 정수로 변환해 foods에 누적한다. 그런 다음 상, 하, 좌, 우 지점도 방문한다. 이때 각 방문은 정해진 구역을 벗어나지 않는다.

 

구현

bool visit(pair<int, int> idx, int& foods, vector<string>& maps, vector<vector<bool>>& visited) {
    int row = idx.first;
    int col = idx.second;

    if (visited[row][col])
        return false;
    else
        visited[row][col] = true;

    char value = maps[row][col];
    if (value == 'X')
        return false;
    else {
        foods += value - '0';
        // 상 (맨 위 행이 아닐 때만)
        if (row != 0) visit({row-1, col}, foods, maps, visited);
        // 하 (맨 아래 행이 아닐 때만)
        if (row != maps.size()-1) visit({row+1, col}, foods, maps, visited);
        // 좌 (맨 왼쪽 열이 아닐 때만)
        if (col != 0) visit({row, col-1}, foods, maps, visited);
        // 우 (맨 오른쪽 열이 아닐 때만)
        if (col != maps[0].size()-1) visit({row, col+1}, foods, maps, visited);
    }

    return true;
}

 

    int row = idx.first;
    int col = idx.second;

 

pair<int, int> idx의 첫 번째 값은 몇 번째 행인지, 두 번째 값은 몇 번째 열인지 정보를 담고 있다. 이 값들을 지역 변수 row, col에 각각 저장한다.

 

    if (visited[row][col])
        return false;
    else
        visited[row][col] = true;

 

인자로 넘겨 받은 visited 배열에는 위치들에 대한 방문 여부가 담겨있다. 이를 통해 해당 (row, col) 위치가 방문된 적이 있는지 확인한다. 이미 방문하였다면 false를 반환하고 종료한다. 방문한 적이 없다면, 해당 지점을 방문하였다고 표시한 뒤 방문 절차를 진행한다.

 

    char value = maps[row][col];
    if (value == 'X')
        return false;
    else {
        foods += value - '0';
        // 상 (맨 위 행이 아닐 때만)
        if (row != 0) visit({row-1, col}, foods, maps, visited);
        // 하 (맨 아래 행이 아닐 때만)
        if (row != maps.size()-1) visit({row+1, col}, foods, maps, visited);
        // 좌 (맨 왼쪽 열이 아닐 때만)
        if (col != 0) visit({row, col-1}, foods, maps, visited);
        // 우 (맨 오른쪽 열이 아닐 때만)
        if (col != maps[0].size()-1) visit({row, col+1}, foods, maps, visited);
    }

 

방문할 위치에 저장된 값을 가져와 value에 저장한다. maps는 vector<string> 타입이기 때문에 maps[row][col]은 char 타입이 된다.

 

value가 'X'라면 그 지점은 바닷가이므로 방문을 종료한다. 'X'가 아니라면 그 지점은 무인도이다. 따라서 그 지점에 저장된 값을 foods에 저장한다.

 

이때 값은 '5', '7'과 같은 char 타입이다. 이 값을 정수로 변환하는 법은 '0'을 빼면 된다. ASCII 코드에서 '0'을 시작으로 1씩 증가하며 정수들이 있기 때문이다.

 

현재 위치의 값을 foods에 누적하였다면 상, 하, 좌, 우 지점을 방문한다. 이때 방문하는 지점은 경계를 넘을 수 없다. 예를 들어, 가장 왼쪽 위 지점이라면, 상, 좌 지점은 방문이 불가능하다.

 

만일 현재 지점이 가장 위 행이라면, 상 지점은 방문이 불가능하다. 가장 아래 행이라면 하 지점은 방문이 불가능하다. 가장 왼쪽 열이라면 좌 지점은 방문이 불가능하다. 가장 오른쪽 열이라면 우 지점은 방문이 불가능하다.

 

위치는 왼쪽 위 지점이 기준점이므로, 가장 위 행일 때는 row == 0일 때이다. 따라서 row != 0일 때만 상 위치를 방문한다. 이때 상 위치는 (row-1, col)이 된다.

 

가장 아래 행일 때는 row == maps.size()-1일 때이다. 따라서 row != maps.size()-1일 때 아래 행인 (row+1, col)을 방문한다.

 

같은 규칙으로 열에 대해서도 방문을 수행한다.

 

    return true;
}

 

상, 하, 좌, 우 모든 지점의 방문이 종료되면 foods에는 각 지점을 통해 방문한 음식의 수가 누적되어 있다. 참조 변수로 전달했기 때문이다. 최종적으로 true를 반환하여 foods에 유의미한 정보가 포함되어 있음을 표시하며 반환한다.

solution() 함수

---

함수 원형

vector<int> solution(vector<string> maps)

 

solution() 함수는 지도를 나타내는 문자열 배열 maps를 인자로 받아 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 반환한다. 만약 지낼 수 있는 무인도가 없다면 [-1]을 반환한다.

 

구현

vector<int> solution(vector<string> maps) {
    // calculate the number of rows, columns
    int rows = (int)maps.size();
    int cols = (int)maps[0].size();

    // record wheather visited or not
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));

    vector<int> answer;
    int foods = 0;
    for (int i = 0; i < rows; i++)
        for (int j = 0; j < cols; j++) {
            foods = 0;
            if (!visited[i][j] && visit({i, j}, foods, maps, visited))
                answer.push_back(foods);
        }

    if (answer.size() == 0)
        answer.push_back(-1);
    else
        sort(answer.begin(), answer.end());
    return answer;
}

 

    int rows = (int)maps.size();
    int cols = (int)maps[0].size();

 

지도의 행과 열의 수를 지역 함수 rows, cols에 저장한다.

 

vector<vector<bool>> visited(rows, vector<bool>(cols, false));

 

(rows, cols) 크기의 false로 채워진 배열을 생성한다.

 

    vector<int> answer;
    int foods = 0;
    for (int i = 0; i < rows; i++)
        for (int j = 0; j < cols; j++) {
            foods = 0;
            if (!visited[i][j] && visit({i, j}, foods, maps, visited))
                answer.push_back(foods);
        }

 

정답을 담을 answer 배열을 선언한다. foods는 한 섬에 대한 총 음식의 수를 저장할 공간이다.

 

이중 for문을 통해 maps의 모든 지점을 인덱스 (i, j)로 방문한다.

 

foods는 섬 단위로 기록하기 때문에 각 방문 직전에는 foods = 0으로 초기화한다.

 

!visited[i][j] && visit({i, j}, foods, maps, visited) 조건에서는 단락 평가가 이루어지기 때문에 해당 지점을 방문하지 않았을 때(!visited[i][j]) visit 함수를 호출한다. 또한 visit 함수의 반환 값이 true인 경우에만 섬을 찾았다는 의미이므로, 그 섬의 모든 음식 수가 저장된 foods를 answer에 push_back()한다.

 

    if (answer.size() == 0)
        answer.push_back(-1);
    else
        sort(answer.begin(), answer.end());
    return answer;

 

이중 for문이 종료되었을 땐 모든 섬에 대한 foods의 정보가 answer에 담겨있다. 이때 answer의 크기가 0이라면, 섬이 하나도 존재하지 않는다는 의미이므로 answer에 -1을 담는다.

 

answer의 크기가 0이 아니라면, 어떤 값이든 존재한다는 의미이므로 이들을 오름차순으로 정렬한다.

 

최종적으로 answer를 반환한다.