백준 2589, 모든 지점에 대한 최단거리를 구해야 하는 완전탐색(BFS)

https://www.acmicpc.net/problem/2589

2589번: 보물섬

해당 문제는 두 육지에 대한 최단거리가 가장 큰 두 지점을 보물 위치로 지정하고, 그 두 곳의 최단거리를 구하는 문제이다.

따라서 필자는 해당 문제를 풀기 위한 전략을 다음과 같이 정했다.

1. DFS(재귀)를 통해 각 육지마다 최단거리를 구한 뒤, 최대 값으로 갱신한다.
2. 갱신할 때마다, 해당 좌표 값을 저장한다.
3. 구한 보물의 위치에 대해서 최단거리를 구하는 BFS 탐색을 진행한다.

필자는 처음에 보물의 위치를 찾는 DFS 함수와 두 보물의 최단거리를 구하는 BFS 함수를 작성하였다. 따라서

코드가 상당히 복잡했고 사용되는 변수들도 많았다. 테스트 케이스는 통과하였지만 제출했을 때 통과하지 못했고,

그 원인을 찾기 위한 디버깅 과정이 어렵게 느껴졌다. 따라서 보다 단순하고 간편하게 짰어야 했다.

 

사실 이 문제는 BFS만으로 바로 해결이 가능한 문제이다. 문제를 잘 읽고 파악했다면 알고리즘을 보다 간편하게 할 수 있었을 것이다. 문제에서 구해야 하는 두 보물 간의 거리는 두 육지 간의 최단거리 중 최대 값으로 해석할 수 있다. 따라서 굳이 보물의 위치를 구하지 않고도 최단거리를 구하는 과정을 통해 정답을 얻을 수 있는 것이다.

 

다만 일반적인 BFS 문제와 다른 점은 BFS를 탐색해야 하는 지점이 여러 곳이라는 것이다. 따라서 육지인 모든 부분에 대한 탐색이 이뤄져야 하며, 이는 완전탐색에 해당한다. 또한 매 BFS 탐색마다 원상복구가 이뤄져야 한다.

 

Key Point

1. 문제를 충분히 읽고 파악한 뒤, 문제에서 원하는 것이 무엇인지 정확히 파악한다.
2. 문제풀이 전략이 생각 이상으로 복잡할 경우, 보다 간편한 방법은 없을 지 한번 더 고민해봐야 한다.
3. 육지를 탐색할 때마다 최단거리의 최대 값을 갱신해야 하며, 보물의 위치를 알 필요는 없다.
4. 매 BFS 마다 방문 배열을 초기화 해야 이전 값에 대한 영향을 받지 않는다. (원복)
5. BFS에서 최단거리를 구하는 핵심 로직인 visited[ny][nx] = visited[y][x] + 1을 잘 활용한다.

 

문제 코드

#include <bits/stdc++.h>
using namespace std;
int n, m, mx, visited[54][54];
const int dy[] = {-1, 0, 1, 0}; 
const int dx[] = {0, 1, 0, -1}; 
char a[54][54];

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()){
		tie(y, x) = q.front(); 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) continue;
			if(visited[ny][nx] || a[ny][nx] == 'W') continue;
			
			// 최단거리를 구하는 핵심 로직 
			visited[ny][nx] = visited[y][x] + 1;
			q.push({ny, nx});
			
			// 매 탐색마다 최단거리를 최대값으로 갱신 
			mx = max(mx, visited[ny][nx]);
		}
	}

	return ;
}

int main(){
	
	cin >> n >> m;
	for(int i = 0 ; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> a[i][j];
		}
	}
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(a[i][j] == 'L') bfs(i, j);
		}
	}
	
	cout << mx - 1 << "\n"; 

	return 0;
}

• 육지인 지점에 대해서 모두 BFS를 실행해야 하므로, for문과 if문을 활용한다.
  • 따라서 BFS 로직을 하나의 메서드로 빼놓았다.
  • Queue도 매 BFS 마다 초기화되어야 하기 때문에 메서드의 전역변수 영역에 선언하였다.
• Queue의 pop()은 값을 삭제하고 반환하지는 않는다. 따라서 pop한 값을 얻기 위해서는 반환하는 메서드인 front()를 사용해야 한다.
• 최대값을 구하기 위한 초기값 mx는 범위를 벗어나는 값이어야 하므로 0이며, 전역변수 선언시 0으로 초기화 된다.
• BFS를 실행하기 위해서는 시작 위치에 대한 방문 처리 및 Push가 이뤄져야 한다.
  • 시작위치 방문 및 Push
  • while문 (Queue가 빌 때까지) - front() 및 pop()으로 시작
  • 인접노드 Push 및 최단거리 저장 (visited 방문 배열 활용)

 

 

 

 

 

https://www.inflearn.com/course/10%EC%A3%BC%EC%99%84%EC%84%B1-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%81%B0%EB%8F%8C/dashboard

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트 - 인프런 | 강의