백준 23302 전파와 병합 2

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

23302번: 전파와 병합 2

dfs를 사용해 문제를 풀었습니다.

그래프의 사이클 유무를 체크하는 간단한 문제지만 그래프의 연결관계가 문자열로 주어지므로

추가로 문자열처리 파싱이 요구되는 문제였습니다. 저는 문자열을 뒤에서 부터 읽어 진법을 처리하였고

+를 만나면 추가로 연결관계를 기록하게 했습니다. 

사이클 체크는 dfs로 시작점을 인자로 주어 현재위치가 시작점으로 돌아올경우 사이클이 존재한다고 판단하게 처리 했습니다.

#include<stdio.h>
#include<queue>
#include<vector>
#include<iostream>
#include<map>
#include<set>
#include<stack>
#include<algorithm>
using namespace std;
void fast_io() {
  cin.tie(0)->sync_with_stdio(0);
}
int R,C;
vector<vector<vector<pair<int,int>>>> vec;
bool visit[1000][800];
bool solve=false;
void dfs(pair<int,int> src,pair<int,int> now){
    //cout<<src.first<<" "<<src.second<<" "<<now.first<<" "<<now.second<<'\n';
    visit[now.first][now.second]=true;
    for(auto i : vec[now.first][now.second]){
        if(visit[i.first][i.second]){
            if(i.first==src.first && i.second == src.second) solve=true;
        }
        else dfs(src,i);
    }
}
int main(){
    fast_io();
    cin>>R>>C;
    for(int x=0;x<=R;x++){
        vec.push_back(vector<vector<pair<int,int>>>());
        for(int y=0;y<=C;y++) {
            vec[x].push_back(vector<pair<int,int>>());
        }
    }
    for(int x=1;x<=R;x++){
        for(int y=1;y<=C;y++){
            string temp;
            cin>>temp;
            if(temp[0]=='.') continue;
            int r1=0;
            int c1=0;
            int r2=0;
            int c2=0;
            int sl=(int)temp.size();
            int nn=1;
            int aa=1;
            bool chk=false;
            for(int x=sl-1;x>=0;x--){
                if('0'<=temp[x] && temp[x]<='9'){
                    if(!chk) r1+=(temp[x]-'0')*nn;
                    else r2+=(temp[x]-'0')*nn;
                    nn*=10;
                }
                if('A'<=temp[x] && temp[x]<='Z'){
                    if(!chk) c1+=(temp[x]-'A'+1)*aa;
                    else c2+=(temp[x]-'A'+1)*aa;
                    aa*=26;
                }
                if(temp[x]=='+'){
                    chk=true;
                    nn=1;
                    aa=1;
                }
            }
            vec[r1][c1].push_back({x,y});
            if(chk) vec[r2][c2].push_back({x,y});
            //cout<<temp<<'\n';
            //cout<<r1<<" "<<c1<<" "<<r2<<" "<<c2<<" "<<x<<" "<<y<<'\n';
        }
    }
    for(int x=1;x<=R;x++){
        for(int y=1;y<=C;y++){
            if(!visit[x][y]){
                dfs({x,y},{x,y});
            }
        }
    }
    if(solve) cout<<"yes";
    else cout<<"no";
}