문제 풀이 과정을 공유하고자 한다.
문제 출처

1. 문제설명

  • 최대 100 크기의 정사각형 지도가 주어진다.
  • 각 칸은 X 또는 1~9까지의 숫자 중 하나이며 각각 바다, 무인도를 나타낸다.
  • 상,하,좌,우로 연결되는 땅들은 하나의 무인도를 이룬다고 가정
  • 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타낸다.
  • 각 섬에서 최대 며칠씩 머물 수 있는지 알아보자
    • 섬이 여러개라면, 오름차순으로 정렬
    • 섬이 없다면, -1



2. 알고리즘 설계

  • 맵의 전체를 탐색하면서 숫자가 아닌 칸을 BFS 탐색한다.
    • 탐색 중에 방문한 점은 visited를 이용해 체크한다.



3. 로직

  • BFS 탐색 영역을 모두 더해야 한다.
    • visited에서 체크된 영역은 건너뛰고,
    • 그 외에 한번 지나간 영역은 변수에 더해준다.
  • BFS가 한번 수행될 때마다, 무인도 영역을 하나씩 탐색한 것
    • 따라서 BFS 리턴 값을 벡터에 누적시킨다.
  • 오름차순으로 출력해야하므로, 정렬된 벡터를 sort


4. 전체 코드

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

using namespace std;
using pii = pair<int, int>;

const int dy[] = { -1,1,0,0 };
const int dx[] = { 0,0,-1,1 };

bool visited[100][100] = { false, };
int x_len, y_len;

int bfs(vector<string> maps, int sy, int sx, int cost)
{
	int ret = 0;

	queue<pii> q;
	q.push({ sy, sx });
	visited[sy][sx] = true;
	ret += cost;

	while (!q.empty()) {
		pii cur = q.front();
		q.pop();

		for (int dir = 0; dir < 4; dir++) {
			int ny = cur.first + dy[dir];
			int nx = cur.second + dx[dir];

			if (ny < 0 || nx < 0 || ny >= y_len || nx >= x_len)
				continue;
			if (maps[ny][nx] != 'X' && !visited[ny][nx]) {
				q.push({ ny,nx });
				visited[ny][nx] = true;
				ret += (maps[ny][nx] - '0');
			}
		}
	}

	return ret;
}

vector<int> solution(vector<string> maps)
{
	vector<int> ret;
	y_len = maps.size();
	x_len = maps[0].size();

	for (int y = 0; y < y_len; y++) {
		for (int x = 0; x < x_len; x++) {
			if (maps[y][x] != 'X' && !visited[y][x]) {
				int temp = bfs(maps, y, x, (maps[y][x] - '0'));
				ret.push_back(temp);
			}
		}
	}

	sort(ret.begin(), ret.end());
	return (ret.size() ? ret : vector<int>{-1});
}


5. 소감

  • 프로그래머스 2단계 안 푼 문제 순서대로 풀이하고 있는데,
  • BFS 관련 문제가 대부분이다.
  • BFS는 어느정도 풀이가 가능하니,
  • 우선은 다른 유형의 알고리즘(DP, Greedy 등)부터 풀이해야겠다.