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

문제 링크

 프로그래머스

자세한 문제 설명은 링크를 통해 확인하자!!

풀이법

풀이는 너비우선탐색(BFS)으로 풀었다.

개인적으로 깊이우선탐색(DFS)보단 너비우선탐색(BFS)를 선호한다.

입출력 예제로 준 예시를 보면서 설명하겠다.

좌측 상단부터 우측으로 하나씩 확인하면서 우측 하단까지 탐색할 것이고 처음으로 발견한 숫자(위에선 5)를 큐(Queue)에 삽입할 것이다.

삽입 후에 아래 순서를 큐가 비워질 때까지 반복해서 진행할 것이다.

여기서 중요한 점은 데이터가 중복이 되는 숫자이기 때문에 이미 지나간 곳인지 확인하려면 숫자 값 대신 행, 열 값을 넣어야 한다.

1. 큐에서 데이터(이하 A(row,col))를 꺼냄
2. A가 이미 방문한 곳인지 확인 -> 방문했다면 1부터 다시 진행
3. SUM += A
4. A를 방문한 곳으로 처리
5. A 기준으로 상,하,좌,우에 ‘X’ 가 아닌 값이 있다면 큐에 삽입

큐 변화 모습
한 스텝이 진행될 때마다 맨 앞에 데이터를 꺼내서 상,하,좌,우에 다른 값이 있는지 확인한다.

| (0,1) |   |   |   | | — | — | — | — |

| (1,1) | (0,2) |   |   | | — | — | — | — |

| (0,2) | (2,1) |   |   | | — | — | — | — |

| (2,1) | (0,3) |   |   | | — | — | — | — |

큐가 전부 비워지게 되면 처음 시작한 숫자의 위치를 기준으로 연결된 모든 곳을 탐색할 수 있게 된다.

전체 코드

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

using namespace std;

int GetResult(int sum, 
    const int startRow, 
    const int startCol, 
    const vector<string>& maps, 
    vector<tuple<int, int>>& already)

{
    if (startRow < 0 || startRow >= maps.size())
        return 0;

    if (startCol < 0 || startCol >= maps[startRow].size())
        return 0;

    if (maps[startRow][startCol] == 'X')
        return 0;


    if (find(already.begin(), already.end(), make_tuple(startRow, startCol)) != already.end())
    {
        return 0;
    }
    else
    {
        queue<tuple<int, int>> queue;

        queue.push(make_tuple(startRow, startCol));

        while (!queue.empty())
        {
            auto data = queue.front();
            queue.pop();

            int row = get<0>(data);
            int col = get<1>(data);

            if (row < 0 || row >= maps.size())
                continue;
            if (col < 0 || col >= maps[row].size())
                continue;
            if (maps[row][col] == 'X')
                continue;
            if (find(already.begin(), already.end(), make_tuple(row, col)) != already.end())
                continue;

            sum += maps[row][col] - '0';
            already.emplace_back(make_tuple(row, col));

            queue.push(make_tuple(row - 1, col));
            queue.push(make_tuple(row + 1, col));
            queue.push(make_tuple(row, col - 1));
            queue.push(make_tuple(row, col + 1));
        }

        return sum;
    }
}

vector<int> solution(vector<string> maps)
{
    vector<int> answer;
    vector<tuple<int,int>> already;

    for (int row = 0; row < maps.size(); row++)
    {
        for (int col = 0; col < maps[row].size(); col++)
        {
            int result = GetResult(0, row, col, maps, already);

            if (result != 0)
                answer.emplace_back(result);
        }
    }

    if (answer.size() == 0)
        answer.emplace_back(-1);

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