반드시 가는 곳 2(please2) (JUNGOL 1672)

https://jungol.co.kr/problem/1672

---

아이디어

그래프로 생각해봅시다. S에서 시작하는 DFS를 돌려봅시다. 만약 어떤 점이 단절점이되는데, 이 점으로 인해 S와 E가 떨어지게 된다면, 그 점은 반드시 지나는 점입니다. 이를 구현해주면 됩니다.

---

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;

vector <ll> Graph[252525];

ll visit[252525]={0},now=0;
bool Include[252525]={0},danjeol[252525]={0};

ll DFS(ll node,ll before)
{
    visit[node]=++now;
    ll mn=now;
    for (ll next:Graph[node])
    {
        if (next==before) continue;
        if (visit[next])
        {
            mn=min(mn,visit[next]);
            continue;
        }
        ll temp=DFS(next,node);
        mn=min(mn,temp);
        
        if (Include[next])
        {
            Include[node]=true;
            if (temp>=visit[node])
                danjeol[node]=true;
        }
    }

    return mn;
}

char grid[555][555]={0};

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,i,j,Start,End;
    
    cin>>N;
    for (i=0;i<N;i++)
    {
        for (j=0;j<N;j++)
        {
            cin>>grid[i][j];
            if (grid[i][j]=='S') Start=i*N+j;
            if (grid[i][j]=='E') End=i*N+j;

            if (i && grid[i][j]!='#' && grid[i-1][j]!='#') Graph[i*N+j].push_back((i-1)*N+j),Graph[(i-1)*N+j].push_back(i*N+j);
            if (j && grid[i][j]!='#' && grid[i][j-1]!='#') Graph[i*N+j].push_back(i*N+j-1),Graph[i*N+j-1].push_back(i*N+j);
        }
    }

    Include[End]=true;
    DFS(Start,-1);

    for (i=0;i<N;i++)
    {
        for (j=0;j<N;j++)
        {
            if (grid[i][j]=='.')
            {
                if (danjeol[i*N+j]) cout<<'o';
                else cout<<'.';
            }
            else cout<<grid[i][j];
        }
        cout<<"\n";
    }
}