백준 15559 내 선물을 받아줘

http://www.acmicpc.net/problem/15559 

15559번: 내 선물을 받아줘

그래프 탐색 문제입니다. NXM 격자에 각자 그  칸에서 가야만 하는 방향이 적혀있는데  최소의 선물을 둬서 어떤 칸에 있더라도 선물이 있는 칸으로 갈 수 있게 하는게 문제입니다.

 

이는 유향 그래프의 연결요소를 구하는 문제와 동일합니다. 모든 칸에 대해 그래프 탐색을 시행하여 방문했던칸들에 대해서는 선물을 두지않고 방문했던 칸에 대해서 선물을 두면 됩니다.

 

이 때 그래프 탐색에서 이 칸으로 올 수 있는 칸들에 대해서도 탐색을 진행하면 됩니다. 저는 dfs로 풀었습니다.

#include<stdio.h>
#include<vector>
#include<math.h>
#include<algorithm>
#include<bitset>
#include<string>
#include<iostream>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<functional>
using namespace std;
void fast_io() {
  cin.tie(0)->sync_with_stdio(0);
}
int ans=0;
bool visit[1001][1001];
char board[1001][1001];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
pair<int,int> m[200];
int N,M;
void dfs(pair<int,int> src,pair<int,int> now){
    if(visit[now.first][now.second]){
        return;
    }
    visit[now.first][now.second]=true;
    if(src==now) ans++;
    char nowc=board[now.first][now.second];
    int nx=now.first+m[nowc].first;
    int ny=now.second+m[nowc].second;
    if(nx>=0 && ny>=0 && nx<N && ny<M) dfs(src,{nx,ny});

    for(int x=0;x<4;x++){
        int cx=dir[x][0]+now.first;
        int cy=dir[x][1]+now.second;
        if(cx<0 || cy<0 || cx>=N || cy>=M) continue;
        if(m[board[cx][cy]].first+cx== now.first && now.second==m[board[cx][cy]].second+cy) dfs(src,{cx,cy});
    }
}
int main(){
    fast_io();
    cin>>N>>M;
    m['N']={-1,0};
    m['S']={1,0};
    m['E']={0,1};
    m['W']={0,-1};
    for(int x=0;x<N;x++){
        cin>>board[x];
    }
    for(int x=0;x<N;x++){
        for(int y=0;y<M;y++) dfs({x,y},{x,y});
    }
    cout<<ans;
}