보물섬

보물섬 처음 제출한 코드

처음에 딱보고 아! BFS로 풀자 했는데 BFS가 생각이 안나서

DFS로 풀다가 시간초과 나서 강의를 들었다.

DFS로 풀때 입력받은 모든 'L'에 대해 2가지를 조합해서

즉 10x10 Map에 'L'이 10개가 있다고 하면은

10C2를 통해 각각의 경우마다 GO를 재귀적으로 돌려 모든 경로를 다 찾은뒤에 최단거리를 구하는 식으로 햇다

당연히 시간초과 날 만하다

그래서 이문제는 좀 단순하게 생각을 다시해보면 그냥 "최단 거리"만 구하면된다.

즉 BFS를 이중 for문으로 돌려서 나오는 최대값을 가져오면 된다.

cpp코드

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define endl "\n"
#define MAX 52
const int INF = 987654321;

int n, m, ret = 0, arr[MAX][MAX], visited[MAX][MAX];
int w = int('W'), l = int('L');
int dy[4] = {0, 1, 0, -1}, dx[4] = {-1, 0, 1, 0};
char c;

bool Cango(int y, int x)
{
    if (y < 0 || x < 0 || y >= n || x >= m || arr[y][x] == w) return false;
    return true;
}

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.empty())
    {
        int ty = q.front().first;
        int tx = q.front().second;
        q.pop();
        for (int i = 0; i < 4; ++i)
        {
            int ny = ty + dy[i];
            int nx = tx + dx[i];
            if (Cango(ny, nx) == false) continue;
            if (visited[ny][nx]) continue;
            visited[ny][nx] = visited[ty][tx] + 1;
            q.push({ny, nx});
            ret = max(ret, visited[ny][nx]);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;

    for (int y = 0; y < n; ++y)
    {
        for (int x = 0; x < m; ++x)
        {
            cin >> c;
            arr[y][x] = int(c);
        }
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (arr[i][j] == l) 
                BFS(i, j);
        }
    }

    cout << ret - 1 << endl;

    return 0;
}