[백준 2589번 / C++] 보물섬

완전 탐색 문제이다. 

 

먼저 map이 [3][4] 배열로 주어진다면 {0,0} ~ {2,3} 까지 총 12개의 좌표값을 하나하나 현위치로 판단해서 갈 수 있는 최대 거리를 구하라는 것이다.  

 

즉, bfs() 를 활용해서 현위치에서 바다가 아닌 육지로 갈 수 있는 거리를 계속해서 갱신하고 최댓값을 구해나가는 것이다. 

 

map[3][4]가 주어진다고 가정을 하고, "W = 0 , L = 1" 라고 보기 쉽게 숫자로 표현하였다.

그리고 map 크기만큼 check 라는 배열을 생성 해준다.

 

먼저 {0,3} 지점을 먼저 살펴보자. 

다음 그림을 보면 현위치에서 갈 수 있는 길이 있을 때마다 숫자를 갱신해나간다. 

모든 맵을 다 살펴보고 나면 최댓값이 3이라는 것을 알 수 있다. 그렇기 때문에  result라는 표에서 {0,3} 지점에서의 숫자는 {0,3}라는 현위치에서 갈 수 있는 최대 거리라고 생각하면 된다. 

 

실제 구현에서는 result 배열을 따로 생성하지 않고 최댓값인지 비교를 해서 구현을 하였다. 

또한, 첫 시작점의 거리값을 1로 설정을 해두었기 때문에 결과를 출력할 때는 result-1 을 출력하도록 하였다. 

 

#include <iostream>
#include <queue>
#include <tuple>
using namespace std; 
int map[50][50]; 
int check[50][50]; 
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 }; 
int h, w;
int result = -1; 
queue <pair<int, int>> q; 
void bfs() {
	int x, y, nx, ny;
	while (q.size()) {
		tie(y, x) = q.front();
		q.pop(); 
		for (int i = 0; i < 4; i++) {
			nx = x+ dx[i]; 
			ny = y+ dy[i]; 
			if (nx < 0 || nx >= w || ny < 0 || ny >= h)continue; //map 범위 넘었을 때
			if (map[ny][nx] == 0 || check[ny][nx])continue; //바다거나 이미 체크된곳이면
			check[ny][nx] = check[y][x] + 1;//현지점+1 값을 조건 만족시 상하좌우에 갱신.
			result = max(check[ny][nx], result); //result 값 비교해서 최댓값이면 갱신.
			q.push({ ny,nx }); //queue에 다시 집어넣기
		}
	}
}

int main() {
	cin >> h >> w; 
	for (int i = 0; i < h; i++) {
		string s = ""; cin >> s; 
		for (int j = 0; j < w; j++) {
			if (s[j] == 'W')map[i][j] = 0; 			
			else map[i][j] = 1; 			
		}
	}
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (map[i][j] == 1) {
				check[i][j] = 1; 
				q.push({ i,j });
				bfs(); 
				for (int k = 0; k < h; k++) {
					for (int z = 0; z < w; z++) {
						check[k][z] = 0; 
					}
				}
			}
		}
	}
	cout << result-1; 
}

2589번: 보물섬