알고리즘 :: 백준 :: 2589 - 보물섬

 

 

 

❔문제

🔗문제링크

🔄 문제 및 입출력 조건 파악

• 가로, 세로 ≤ 50

✏️ 문제풀이

육지칸 중에서 서로 다른 두 점을 골랐을 때, 가장 먼 거리를 구하는 문제입니다.
이때, 일부러 돌아가서는 안 되고, 무조건 최단거리로 갔을 때의 거리 기준입니다.

 

두 정점 사이의 최단거리를 구해야 하므로 가장 먼저 BFS를 떠올립니다.

 

로직은 다음과 같습니다.

1. 모든 육지칸의 좌표를 `queue<pair<int, int>>`에 저장합니다.
2. 이 큐가 모두 빌 때까지 while문을 돌리는데,
3. 각 육지칸을 시작점으로 BFS를 돌립니다.
4. BFS를 하면서 외부 배열에 방문여부 및 거리를 기록합니다.
5. BFS를 마쳤다면 다시 전체 맵을 검사해 가장 거리가 길 때를 찾고 답을 갱신합니다.

위 로직을 코드로 구현하면 다음과 같습니다.

for (const auto& land : lands) {
    memset(&dist[0][0], 0, sizeof(dist));
    bfs(land.first, land.second);
    ans = max(ans, getDist());
}

 

백트래킹

사실 모든 육지칸을 검사할 필요가 없습니다.

글로는 조금 이해하기 힘들 수 있어서 그림을 보면서 이해해봅시다.

가장 왼쪽 그림을 봅시다. 왼쪽, 위쪽이 막혀있기 때문에 아래, 오른쪽으로 BFS를 이어서 진행합니다.

 

가운데 그림을 봅시다. 막혀있는 위쪽을 제외하고 BFS를 진행했을 겁니다. 그러나, 왼쪽은 진행할 필요가 없다는 것을 바로 알 수 있습니다. 왜냐하면, 저희는 육지칸 좌표를 queue에 `push()` 할 때, 행은 위에서 아래로, 열은 왼쪽에서 오른쪽으로 순회하며 넣었기 때문입니다. 따라서 이미 왼쪽칸에서 BFS를 진행했기 때문에 최단거리가 아니라 돌아가는 길이 됩니다.

 

가장 오른쪽 그림을 봅시다. 오른쪽은 막혀서 못 가고, 왼쪽과 위쪽은 방금 설명했듯 중복이 되므로 갈 필요가 없습니다. 아래 방향만 유효합니다. 그리고 아래 방향은 바로 윗칸을 시작점으로 탐색할 때가 더 거리가 클 것이기 때문에 역시 탐색할 필요가 없습니다.

 

이러한 논리로 갈 수 있는 방향이 3개 이상이면 무조건 그 칸보다 왼쪽이든 윗쪽이든 먼저 탐색한 칸이 존재하게 됩니다. 그리고 그 칸들을 시작점으로 BFS를 돌렸을 때, 최대거리를 찾을 가능성이 높습니다. 따라서 갈 수 있는 방향을 카운트 했을 때, 1개 또는 2개인 육지칸에 대해서만 BFS를 돌리면 됩니다.

while (!lands.empty()) {
    int y, x; tie(y, x) = lands.front();
    lands.pop();
    
    // 유효한 방향 개수 검사
    int dirCount = 0;
    for (int i = 0; i < 4; ++i) {
        int ny = y + dy[i], nx = x + dx[i];
        if (isValid(ny, nx) && arr[ny][nx]) dirCount++;
    }
    // 갈 수 있는 방향이 1개 또는 2개
    if (dirCount <= 2) {
        memset(&dist[0][0], 0, sizeof(dist));
        bfs(y, x);
        ans = max(ans, getDist());
    }
}

📝 코드

#include <bits/stdc++.h>
using namespace std;

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

int N, M, ans;
array<array<uint8_t, 51>, 51> arr;
array<array<int, 51>, 51> dist;
vector<pair<int, int>> lands;

inline int getDist() {
	int ret = 0;
	for (int y = 0; y < N; ++y)
		for (int x = 0; x < M; ++x)
			if (arr[y][x]) ret = max(ret, dist[y][x]);
	return ret;
}

void bfs(int sy, int sx) {
	queue<pair<int, int>> q;
	q.push({sy, sx});
	dist[sy][sx] = 1;
	while (!q.empty()) {
		int y, x; tie(y, x) = q.front();
		q.pop();
		for (int i = 0; i < 4; ++i) {
			int ny = y + dy[i], nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
			if (arr[ny][nx] == 0 || dist[ny][nx] != 0) continue;
			dist[ny][nx] = dist[y][x] + 1;
			q.push({ny, nx});
		}
	}
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin >> N >> M;
	for (int y = 0; y < N; ++y) {
		string line;
		cin >> line;
		for (int x = 0; x < M; ++x) {
			if (line[x] == 'L') { 
				lands.push_back({y, x});
				arr[y][x] = true;
			}
		}
	}
	for (const auto& land : lands) {
		memset(&dist[0][0], 0, sizeof(dist));
		bfs(land.first, land.second);
		ans = max(ans, getDist());
	}
	cout << ans - 1;
}

 

🔗 코드 링크

 

백트래킹 적용

#include <bits/stdc++.h>
using namespace std;

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

int N, M, ans;
array<array<uint8_t, 51>, 51> arr;
array<array<int, 51>, 51> dist;
queue<pair<int, int>> lands;

inline bool isValid(int y, int x) {
	return (0 <= y) && (y < N) && (0 <= x) && (x < M);
}

inline int getDist() {
	int ret = 0;
	for (int y = 0; y < N; ++y)
		for (int x = 0; x < M; ++x)
			if (arr[y][x]) ret = max(ret, dist[y][x]);
	return ret;
}

void bfs(int sy, int sx) {
	queue<pair<int, int>> q;
	q.push({sy, sx});
	dist[sy][sx] = 1;
	while (!q.empty()) {
		int y, x; tie(y, x) = q.front();
		q.pop();
		for (int i = 0; i < 4; ++i) {
			int ny = y + dy[i], nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
			if (arr[ny][nx] == 0 || dist[ny][nx] != 0) continue;
			dist[ny][nx] = dist[y][x] + 1;
			q.push({ny, nx});
		}
	}
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin >> N >> M;
	for (int y = 0; y < N; ++y) {
		string line;
		cin >> line;
		for (int x = 0; x < M; ++x) {
			if (line[x] == 'L') { 
				lands.push({y, x});
				arr[y][x] = true;
			}
		}
	}
	while (!lands.empty()) {
		int y, x; tie(y, x) = lands.front();
		lands.pop();
		
		int dirCount = 0;
		for (int i = 0; i < 4; ++i) {
			int ny = y + dy[i], nx = x + dx[i];
			if (isValid(ny, nx) && arr[ny][nx]) dirCount++;
		}
		if (dirCount <= 2) {
			memset(&dist[0][0], 0, sizeof(dist));
			bfs(y, x);
			ans = max(ans, getDist());
		}
	}
	cout << ans - 1;
}

🔗 코드 링크

🕧 결과