[백준/C++] 16929번_Two Dots

문제는 다음과 같습니다.

에러 10번내고 풀었던 풀이입니다.
좀 어렵네용
저는 처음에 bfs로 접근했다가, dfs로 접근해야한다는 힌트를 얻고 다시 풀었습니다.

❗️문제의 핵심은 다음과 같습니다.❗️

• 사이클이 존재한다 -> dfs를 시작한 지점으로 다시 돌아오는 경우가 존재한다.

"dfs에서 상, 하, 좌, 우 이동 시에

출발했던 부분을 제외한 다른 부분으로 이동한다.

이렇게 dfs를 수행했을 때, 이미 방문했던 지점을 재방문하는 경우가 사이클이 형성되는 경우이다."

dfs를 재귀적으로 수행할 시에 만족해야하는 조건은 다음과 같습니다.

✅ 배열에 동일한 문자가 들어간다. (동일 색깔 만족)

✅ 범위를 만족한다. (0<=행<=n, 0<=열<=m)

✅ 이전에 출발했던 부분을 제외한 다른 부분으로 이동한다.

(ex, (0, 0)➡️(0, 1)➡️(0, 0) 이런 경우를 의미합니다 : ↩️ 딱 이 기호)

---

전체 코드는 다음과 같습니다.

#include <bits/stdc++.h>
 using namespace std;

 char a[52][52]={0, };
 int ch[52][52]={0, };
 int n, m; bool state=0;

 bool DFS(int i1, int i2, int o1, int o2, char c){
   if(ch[i1][i2]) return true;

   ch[i1][i2]=1;

   if(a[i1+1][i2]==c && i1+1<=n && !(i1+1==o1 && i2==o2)){
     bool res = DFS(i1+1, i2, i1, i2, c);
     if(res) return true;
   }
   if(a[i1][i2+1]==c && i2+1<=m && !(i1==o1 && i2+1==o2)){
     bool res = DFS(i1, i2+1, i1, i2, c);
     if(res) return true;
   }
   if(a[i1-1][i2]==c && i1-1>=0 && !(i1-1==o1 && i2==o2)){
     bool res = DFS(i1-1, i2, i1, i2, c);
     if(res) return true;
   }
   if(a[i1][i2-1]==c && i2-1>=0 && !(i1==o1 && i2-1==o2)){
     bool res = DFS(i1, i2-1, i1, i2, c);
     if(res) return true;
   }

   return false;
 }




 int main() {
     ios_base::sync_with_stdio(false);
     cin.tie(nullptr);

     cin>>n>>m;
     for(int i=1; i<=n; i++){
       string str; cin>>str;
       for(int j=0; j<str.size(); j++){
         a[i][j+1]=str[j];
       }
     } // 입력 끝

     for(int i=1; i<=n; i++){
       for(int j=1; j<=m; j++){

         if(ch[i][j]==0){
           state = DFS(i, j, 0, 0, a[i][j]);
           if(state){
             cout<<"Yes";
             return 0;
           }
         }

       }
     }
     cout<<"No";
     return 0;
 }

---

2/19 토요일 복습)

#include <bits/stdc++.h>
using namespace std;

int n, m;
char a[52][52]={0, }; int ch[52][52]={0, };

bool DFS(int c1, int c2, int e1, int e2, char k){
  if(ch[c1][c2]==1) return true;
  ch[c1][c2]=1;

  if(c1+1<=n && a[c1+1][c2]==k && !(c1+1==e1 && c2==e2)){
    bool res = DFS(c1+1, c2, c1, c2, k);
    if(res) return true;
  }
  if(c2+1<=m && a[c1][c2+1]==k && !(c1==e1 && c2+1==e2)){
    bool res = DFS(c1, c2+1, c1, c2, k);
    if(res) return true;
  }
  if(c1-1>=1 && a[c1-1][c2]==k && !(c1-1==e1 && c2==e2)){
    bool res = DFS(c1-1, c2, c1, c2, k);
    if(res) return true;
  }
  if(c2-1>=1 && a[c1][c2-1]==k && !(c1==e1 && c2-1==e2)){
    bool res = DFS(c1, c2-1, c1, c2, k);
    if(res) return true;
  }
  return false;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  cin>>n>>m;
  for(int i=1; i<=n; i++){
    string str; cin>>str;
    for(int j=0; j<str.size(); j++){
      a[i][j+1]=str[j];
    }
  }

  for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
      if(ch[i][j]==0){
        if(DFS(i, j, 0, 0, a[i][j])) { cout<<"Yes"; return 0; }
      }
    }
  }
  cout<<"No";
  return 0;
}