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

문제링크:https://www.acmicpc.net/problem/2589

2589번: 보물섬

 

 

최단거리 탐색을 할때는 bfs 알고리즘을 사용합니다.

보물위치의 최단거리를 출력하는 문제였습니다. 

어느지점을 기준으로 출발하느냐에 따라 결과가 달라지기에 조금 생각해야하는 문제였습니다.

 

 

근데 높이,너비가 50까지임으로 저는 모든점에서의 최장거리를 계산해서 문제의 답을 구했습니다.

 

 

한가지 예외처리를 못했던 테스트케이스입니다.

4 4

LLWW

WWWW

WWWW

WWWW

 

이경우 1이 나와야하지만 

간혹 2가 나오는 코드들이 있습니다.

조건문에 (a!= y + de_y[i] || b != x + de_x[i])를 추가해줌으로써 해결했습니다. (출발지점으로 되돌아 오면 안되기 때문에)

 

 

 

기존의 bfs문제들을 풀어보셨다면 쉬운문제였을겁니다.

정답코드입니다. 직접 손으로 작성해보세요 :) 화이팅

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
int height, width;

string arr[51];
int visited[51][51];
int que[2501][2];
int started,ended;
int de_x[4] = { 1, 0, 0,-1 };
int de_y[4] = { 0, 1,-1, 0 };
int result = 0;

void bfs(int a, int b) {
	started = 0, ended = 0;
	que[ended][0] = a;
	que[ended][1] = b;
	ended++;

	while (started != ended) {
		int y = que[started][0];
		int x = que[started++][1];
		
		for (int i = 0; i < 4; i++) {
			if ((y + de_y[i])>=0 && (y + de_y[i])<height && (x + de_x[i])>=0 && (x + de_x[i])<width)
				if (arr[y + de_y[i]][x + de_x[i]] == 'L' && !visited[y + de_y[i]][x + de_x[i]] && (a!= y + de_y[i] || b != x + de_x[i]))
				{
					visited[y + de_y[i]][x + de_x[i]] = visited[y][x] + 1;
					que[ended][0] = y + de_y[i];
					que[ended++][1] = x + de_x[i];
					
				}

		}
		
	}

	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			if (arr[i][j] == 'W') continue;
			if (result < visited[i][j] ) result = visited[i][j];
		}
	}


}
int main() {

	cin >> height >> width;
	for (int i = 0; i < height;i++)
		cin >> arr[i];

	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			if (arr[i][j] == 'W') continue;
			memset(visited, 0, sizeof(visited));
			
			bfs(i,j);


		}
	}

	cout << result << endl;
}