[백준 2589] 보물섬

하루에 하나 알고리즘

누군가에게 조금이라도 도움이 됫으면 하는 바램으로 이 글을 작성합니다

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

풀이

dfs로 풀다가 왜 안풀리지 어떻게하면 분기점에서 다시 시작할 수 있을까 고민을 했는데 답이 안나왔습니다.

이미 ans의 최고 값은 돌아간 곳에서 정해졌으니깐요

그래서 bfs로 푸니깐 한번에 풀렸네요 ㅠㅠㅠㅠㅠ

기본저거인 bfs문제였습니다

소스코드 

#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
int n, m;
int map[51][51];
int visit[51][51];
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,-1,0,1 };
int ans = 0;
queue<pair<int, int>> q;
 
void dfs(int r, int c)
{
    q.push(make_pair(r, c));
    visit[r][c] = 1;
    while (!q.empty())
    {
        
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        if (ans < visit[x][y])
        {
            ans = visit[x][y];
 
        }
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dr[i];
            int ny = y + dc[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m)
                continue;
 
            if (map[nx][ny] == 0 && visit[nx][ny] == 0)
            {
                visit[nx][ny] = visit[x][y] + 1;
                q.push(make_pair(nx, ny));
            }
        }
    }
}
int main()
{
    cin >> n >> m; 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            char ch;
            cin >> ch;
            if (ch == 'W')
            {
                map[i][j] = 1;
            }
            else
                map[i][j] = 0;
        }
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            
            if (map[i][j] == 0)
            {
                memset(visit, 0, sizeof(visit));
                visit[i][j] = 1;
                dfs(i, j);
 
        
            }
        }
    }
    cout << ans-1 << endl;
    return 0;
 
}