프로그래머스 - 무인도 여행 (C++)

Pixabay로부터 입수된 MustangJoe님의 이미지 입니다.

 

---

 

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

프로그래머스

 

 이번 문제는 지도가 주어졌을 때, 'X'를 제외한 영역(섬)의 숫자 합들을 오름차순으로 정렬한 vector를 구하는 문제이다. 이 문제는 전형적인 BFS 문제라고 생각한다. BFS는 간단히 말해 특정 노드와 연결된 노드들을 모두 탐색해 나가는 방법이다. 자세한 설명은 구글링을 통해 쉽게 얻을 수 있으니 생략한다. 

 앞에서 말했듯, 전형적인 BFS 문제로 대략적인 풀이 과정은 다음과 같다.

1. 모든 노드를 반복문을 통해 탐색할 수 있는지 없는지 검사하고 탐색을 시작한다.
   1. 만약 해당 노드를 방문한 적이 없으면서, 노드의 값이 탐색할 수 있는 값이면 이 노드를 시작으로 탐색한다. 이 때, 탐색에는 큐를 이용한다.
   2. 반복문을 통해 나아갈 수 있는 방향의 다음 노드를 검사한다. 다음 노드를 방문한 적이 없으면서, 탐색할 수 있는 값을 가지고 있으면 다음 노드도 큐애 push한다.
2. 탐색이 끝나고 따로 저장햐야 할 값이 있다면 저장한다.

해당 과정을 이 문제에 적용해보자.

• 모든 노드 => 노드 하나는 주어진 maps의 값 하나로 maps[r][c]이다. (0 <= r < maps.size(), 0 <= c < maps[0].size())
• 해당 노드를 방문한 적이 없으면서 => 방문 여부를 저장할 변수를 통해 방문을 했는지 안했는지 저장한다. 아래의 코드에서는 islandId라는 int 타입의 2차원 배열을 이용하였다.
• 노드의 값이 탐색할 수 있는 값 => maps[r][c]에서 r, c가 0 <= r < maps.size(), 0 <= c < maps[0].size()를 충족하면서 maps[r][c]의 값이 'X'가 아닐 때
• 나아갈 수 있는 방향 => 상, 하, 좌, 우

이것들을 고려한 코드는 다음과 같다.

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 101
using namespace std;

int R, C;
int id = 0;
int islandId[MAX][MAX];
vector<string> islands;

int nr[4] = { 1, -1, 0, 0 };
int nc[4] = { 0, 0, 1, -1 };

bool IsIn(int r, int c)
{
    return 0 <= r && r < R && 0 <= c && c < C;
}

int IslandDay(int r, int c)
{
    int daySum = 0;
    int currentId = id++;
    
    queue<pair<int, int>> q;
    q.push({ r, c });
    
    islandId[r][c] = currentId;
    
    while(!q.empty())
    {
        int curR = q.front().first;
        int curC = q.front().second;
        q.pop();
        
        daySum += (islands[curR][curC] - '0');
        
        for (int i = 0; i < 4; ++i)
        {
            int nxtR = curR + nr[i];
            int nxtC = curC + nc[i];
            
            if (IsIn(nxtR, nxtC))
            {
                if (islandId[nxtR][nxtC] == -1 && islands[nxtR][nxtC] != 'X')
                {
                    islandId[nxtR][nxtC] = currentId;
                    q.push({ nxtR, nxtC });
                }
            }
        }
    }
    
    return daySum;
}

vector<int> solution(vector<string> maps) {
    vector<int> answer;
    
    islands = maps;
    
    R = maps.size();
    C = maps[0].size();
    
    for (int r = 0; r < MAX; ++r)
    {
        for (int c = 0; c < MAX; ++c)
            islandId[r][c] = -1;
    }
    
    for (int r = 0; r < R; ++r)
    {
        for (int c = 0; c < C; ++c)
        {
            if (islandId[r][c] == -1 && islands[r][c] != 'X')
            {
                int daySum = IslandDay(r, c);
                
                answer.push_back(daySum);
            }
        }
    }
    
    if (answer.size() == 0)
        return { -1 };
    
    sort(answer.begin(), answer.end());
    
    return answer;
}

---

BFS(Breadth First Search, 너비 우선 탐색)

https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전