[백준] 2589 보물섬 (복습) + Structured Binding in C++17 with Tuple

문제

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다.

예를 들어 위와 같이 지도가 주어졌다면 보물은 아래 표시된 두 곳에 묻혀 있게 되고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다.

보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 가로, 세로의 크기는 각각 50이하이다.

출력

첫째 줄에 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력한다.

 

#include<bits/stdc++.h>

using namespace std;
int n, m;
vector<vector<int>>mp(50, vector<int>(50, 0));
vector<int>ans;
int dy[4] = { -1,0,1,0 }, dx[4] = { 0,1,0,-1 };
int visited[50][50];

void bfs(int y, int x) {
	queue<pair<int, int>>q;
	q.push({ y,x });
	memset(visited, -1, sizeof(visited));
	visited[y][x] = 0;
	while (!q.empty()) {
		auto top = q.front();
		int y = top.first;
		int x = top.second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny >= 0 && ny < n && nx >= 0 && nx < m) {
				if (mp[ny][nx] == 1 && visited[ny][nx] == -1) {
					visited[ny][nx] = visited[y][x] + 1;
					q.push({ ny,nx });
				}
			}
		}		
	}
	int mx = -1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			mx = max(mx, visited[i][j]);
		}
	}
	ans.push_back(mx);
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	char c;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> c;
			if(c=='L')
				mp[i][j]=1;
		}
	}
	//0은 바다 1은 땅

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if(mp[i][j]==1)
				bfs(i,j);
		}
	}
	cout << *max_element(ans.begin(), ans.end());
	return 0;
}

골드 5 BFS 브루트포스 문제입니다.

모든 육지에 대해서 bfs를 수행해서 최단거리 중 가장 먼 거리를 찾으면 됩니다.

 

숏코딩을 보다가 비슷한 풀이를 발견했습니다.

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

char dat[55][55];
bool visit[55][55];

#define F(c,d) if(dat[x+c][y+d]=='L'&&!visit[x+c][y+d])visit[x+c][y+d]=true,que.emplace(x+c,y+d,w+1);

int bfs(int a, int b)
{
	memset(visit, 0, sizeof(visit));
	queue<tuple<int, int, int>> que;
	visit[a][b] = true;
	que.emplace(a, b, 0);
	int ret = 0;
	while (que.empty() == false)
	{
		int x, y, w;
		tie(x, y, w) = que.front();
		que.pop();
		ret = w;
		F(1, 0)
			F(-1, 0)
			F(0, 1)
			F(0, -1)
	}
	return ret;
}

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%s", dat[i] + 1);

	int ans = 0;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (dat[i][j] != 'L') continue;
			ans = max(ans, bfs(i, j));
		}
	}

	printf("%d\n", ans);
}

큐에 튜플을 넣고, BFS를 수행한 코드입니다.

큐의 front 요소에 접근하기위해 tie를 사용하였으나, structured binding을 이용하면 auto를 이용해 바로 요소에 접근할 수 있습니다.

 

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

int main() {
	vector<pair<int, int>>pvt;
	vector<tuple<int, int, int>>tvt;

	int n, m, a, b, c;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		pvt.push_back({ a,b });
	}

	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		tvt.push_back({ a,b,c });
	}

	for (int i = 0; i < n; i++) {
		auto [A, B] = pvt[i];
		cout << A << " " << B << "\n";
	}
	for (int i = 0; i < m; i++) {
		auto [A, B, C] = tvt[i];
		cout << A << " " << B << " " << C << "\n";
	}
}

이렇게 auto [A,B]=pvt[i]를 사용하면 ,A와 B에 자동으로 first ,second값이 저장이 됩니다.

튜플도 마찬가지입니다.