[2589번] 보물섬

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS

전형적인 BFS 문제이다.

여기서 잠깐 BFS와 DFS를 이야기 해보자면, 매번 느끼고 있는 것이지만, DFS가 이용 할 수 있는 범위가 더 넓은 것 같고, BFS는 한정적인것 같다. 

이 문제는 0,0 ~ n-1,m-1 까지 모든 경우를 시작점으로 하여 최단 거리 중 가장 max인 값을 잡으면 된다.

최대 N이 50이기에 충분히 해결 할 수 있다.

O(50*50*50)이어도 충분히 해결이 된다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78

#include <iostream> #include <cstdio> #include <queue> #include <algorithm> #include <memory.h>   using namespace std;   typedef pair<int, int> pii;   char map[52][52]; bool visit[52][52]; int n, m;   int dy[4] = { -1,1,0,0 }; int dx[4] = { 0,0,-1,1 };   int bfs(int i, int j) {     queue<pair<pii, int>> q;       q.push({{ i, j }, 0});       int get = 0;       while (!q.empty())     {         int y = q.front().first.first;         int x = q.front().first.second;         int cnt = q.front().second;                  q.pop();         if (visit[y][x])             continue;                  get = max(get, cnt);         visit[y][x] = true;           for (int i = 0; i < 4; i++)         {             int hereY = y + dy[i];             int hereX = x + dx[i];               if (map[hereY][hereX] == 'W' || hereY < 0 || hereX < 0 || hereY >= n || hereX >= m || visit[hereY][hereX])                 continue;               q.push({ { hereY,hereX },cnt + 1 });         }     }       return get; }   int main() {     int get;     scanf("%d %d", &n, &m);       for(int i = 0 ; i < n ; i++)         scanf("%s", map[i]);         for (int i = 0; i < n; i++)     {         for (int j = 0; j < m; j++)         {             memset(visit, false, sizeof(visit));             if (map[i][j] == 'L')                 get = max(get, bfs(i, j));         }     }          cout << get;     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus