[C++] 백준(BOJ) - 2589 : 보물섬

18 Oct 2023 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 알고리즘
• 풀이
• 코드
• 평가

문제

백준(BOJ) - 2589 : 보물섬(링크)

알고리즘

1. BFS
2. 완전탐색

풀이

1. 최단거리 찾기 - BFS
2. 여러번의 탐색을 진행할때는 방문처리 배열 초기화
3. 찾은 최단 거리 중 가장 먼 곳 최대값 갱신

코드

// BOJ-2589 : 보물섬
#include<bits/stdc++.h>
using namespace std;

int n, m, mx = -2147000000;

char m_map[51][51];
int visited[51][51];

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

void bfs(int y, int x)
{
	memset(visited, 0, sizeof(visited));
	visited[y][x] = 1;
	
	queue<pair<int, int>> q;
	q.push({ y,x });
	while (q.size())
	{
		pair<int,int> tmp = q.front();
		q.pop();

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

			if (ny < 0 || nx < 0 || ny >= n || nx >= m || m_map[ny][nx] == 'W') continue;
			if (visited[ny][nx]) continue;
			visited[ny][nx] = visited[tmp.first][tmp.second] + 1;
			q.push({ ny,nx });
			mx = max(mx, visited[ny][nx]); // 최대값 갱신
		}
	}
	return;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> m_map[i][j];
		}
	}

	// 입력받은 모든 'L'에 대한 BFS를 완전탐색
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (m_map[i][j] == 'L') bfs(i, j);
		}
	}

	cout << mx - 1 << '\n';
	
	return 0;
}

평가

• void 형 BFS 함수를 만들어 여러번의 BFS를 재사용 할 수 있게 코드를 작성할 수 있다
  • 위의 경우 방문 처리 배열은 항상 초기화 하는 습관
• 최단거리 - BFS