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

이진중·2022년 6월 1일
0

알고리즘

목록 보기
45/76
post-thumbnail

보물섬


문제풀이

  1. 가장 거리가 먼지점을 가장 가깝게 연결한 길이를 구하는 문제이다.
  2. 각각의 지점에 대해 BFS를 쓰면서 최대값을 최신화 해주면 된다.
  3. BFS를 한번한 이후 초기화 시켜주는것도 잊지 말자.

DFS가 아닌, BFS로만 풀 수 있는 이유

dfs는 한번에 깊게 멀리 들어가는 알고리즘 특성상, 가장 효율적으로 길이를 가지 않는다.
예를들어

7 7
LLLLLLL
LLLLLLW
LLLLLWW
LLLLLWW
LLLWWWW
LLWWWWW
LWWWWWW

와 같은 입력이 들어오면 DFS의 최대값은 1번째줄을 왼쪽에서 오른쪽으로 탐색후 2번째줄을 오른쪽에서 왼쪽으로 그다음 3번째줄, 4번째.. 이렇게 최대로 멀리가는 길을 택하게 된다.

BFS같은경우에는 한칸한칸 앞으로 전진해 가기 때문에 비효율적인 동선이 나오지 않는다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>
#include <string.h>
#include <queue>
using namespace std;
#define endl "\n"

#define MAX 50+1
int n, m;
int board[MAX][MAX];
bool visited[MAX][MAX];
int ans;
queue<pair<int, int>> q;
int dy[] = { 0,1,0,-1 };
int dx[] = { 1,0,-1,0 };

void bfs(int y, int x) {
	visited[y][x] = true;
	
	q.push({ y,x });

	while (!q.empty())
	{
		int wy = q.front().first;
		int wx = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int ny = wy + dy[i];
			int nx = wx + dx[i];

			if (nx <1 || nx>m || ny<1 || ny>n)
			{
				continue;
			}

			if (!visited[ny][nx] && board[ny][nx] !=-1)
			{
				int spendTime = board[wy][wx] + 1;
				board[ny][nx] = spendTime;
				if (spendTime > ans)
				{
					ans = spendTime;
				}
				visited[ny][nx] = true;
				q.push({ ny,nx });
			}
		}
	}
}
void reset() {
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			visited[i][j] = false;
			if (board[i][j] != -1)
			{
				board[i][j] = 0;
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	ifstream cin; cin.open("input.txt");

	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			char x;
			cin >> x;
			if (x == 'W')
			{
				board[i][j] = -1;
			}
			else {
				board[i][j] = 0;
			}
		}
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			reset();
			if (board[i][j] == 0)
			{
				bfs(i, j);
			}
		}
	}

	cout << ans;
}

참고

https://www.acmicpc.net/board/view/57667 반례참고

0개의 댓글