(C++) - 백준(BOJ) 16929 : Two dots

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

16929번: Two Dots

cycle을 판별하는 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

행 n, 열 m, 정답 ans, 시작점 sr,sc, 방문여부를 확인할 ck, 방향 dr,dc, board 를 선언하고 입력받습니다.

📔 풀이과정

2중 for loop를 수행하면서 같은 문자끼리 dfs로 방문해줍니다.

1. 인접칸을 방문하면서 dfs함수를 호출해줍니다. 호출당 길이가 1씩 증가합니다.

2. 최소 사이클의 길이는 자기 자신으로 돌아왔을 때 4가 됩니다. 길이가 4이상이면서 자기 자신으로 돌아왔을 때 Yes를 출력 후 프로그램을 종료합니다. 그렇지 않으면 call stack문제로 시간초과가 나게됩니다. 

3. dfs함수를 수행한 후 자기 자신을 다시 0으로 만들어 주어 사이클을 다시 판별할 수 있도록 만들어줍니다.

📔 정답출력

dfs함수 수행 결과로 Yes가 출력되지 않았으면 No를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;

int n, m, ans, sr, sc, ck[51][51];
int dr[] = {0,0,1,-1};
int dc[] = {1,-1,0,0};

char board[51][51];

void dfs(int r, int c, int path){
    if(r == sr && c == sc && path >= 4) {
        cout << "Yes"; 
        exit(0);
        return;
    }

    if(ck[r][c]) return;
    ck[r][c] = 1;

    for(int i = 0; i < 4; i++){
        int nr = r + dr[i];
        int nc = c + dc[i];
        if(board[nr][nc] != board[sr][sc]) continue;
        if(0 > nr || nr >= n || 0 > nc || nc >= m) continue;
        dfs(nr,nc,path+1);
    }

    ck[r][c] = 0;
}

int main(){
    cin >> n >> m;

    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> board[i][j];

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(ck[i][j]) continue;
            sr = i, sc = j;
            dfs(i,j,0);
        }
    }

    cout << "No";
}

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.