[알고리즘] C++ 프로그래머스 무인도 여행

 

프로그래머스 무인도 여행 

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

프로그래머스

풀이 전 나의 생각

BFS를 사용하여 공간을 탐색하는 문제다.

우선 식량이 있는 무인도를 탐색하기 위해선 양방향 탐색이 필요하다.

하지만 양방향 탐색을 하면서 오류가 날만한 상황을 모두 배제해줘야 한다.

 

1. 탐색할 다음 위치가 배열의 크기를 벗어나면 안된다.

2. 탐색할 다음 위치가 방문한 곳이 아니면서 X(바다)가 아니여야 한다.

 

두 조건을 만족할 시 다음 탐색 위치에 방문 표시를 해주고 탐색을 진행 할 큐에 다음 위치 값을 넣어준다.

이 과정을 반복하면서 탐색한 무인도의 식량의 개수를 최종 결과값에 계속 더해주며 무인도의 탐색을 완료했다면

최종 결과값을 반환해주면 어떤 무인도에서 최대 며칠 머무를 수 있는지에 대한 값을 얻을 수 있다.  

 

다른 조건으로 무인도가 존재하지 않을 경우 -1을 출력해줘야 한다.

이 말은 BFS를 진입하지 않았다면 자동적으로 무인도가 없는 것이기 때문에 -1을 최종 결과값에 넣어줘야 한다.

 

마지막으로 오름차순으로 값을 반환해야 하기 때문에 오름차순 정렬을 진행해야 하는 것을 잊으면 안된다.

 

BFS의 전형적인 문제지만 요구하는 조건이 존재하기 때문에 이를 잘 파악하고 푸는 것이 중요하다. 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
using namespace std;
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

bool visit[101][101];


int BFS(int x, int y, vector<string> map)
{
    queue<pair<int, int>>q;
    int res = 0;

    res += map[x][y] - '0';
    visit[x][y] = true;
    q.push({x, y});

    while (!q.empty())
    {
        int qx = q.front().first;
        int qy = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = qx + dx[i];
            int ny = qy + dy[i];

            if (nx < 0 || ny < 0 || nx >= map.size() || ny >= map[x].size()) continue;
            if (!visit[nx][ny] && map[nx][ny] != 'X')
            {
                visit[nx][ny] = true;
                q.push({nx, ny});
                res += map[nx][ny] - '0';
            }
        }
    }
    return res;
}

vector<int> solution(vector<string> maps) {
    vector<int> answer;
    bool bfs_chk = false;
    for (int i = 0; i < maps.size(); i++)
    {
        for (int j = 0; j < maps[i].size(); j++)
        {
            if (maps[i][j] != 'X' && !visit[i][j])
            {
                bfs_chk = true;
                answer.push_back(BFS(i, j, maps));
            }
        }
    }

    if (!bfs_chk) 
    {
        answer.push_back(-1);
        return answer;
    }
    sort(answer.begin(), answer.end());
    return answer;
}