Codeforces Round 290 (Div. 2) - Fox And Two Dots 링크
(????? Difficulty *1500)

문제

n × m 크기의 보드판이 주어지며 각 칸에는 색깔을 가진 점이 있다.
인접한 칸에 같은 색깔이 있으면 선으로 이을 수 있는데, 이 때, 사이클을 이루는 선이 있는지 판별

알고리즘

DFS

풀이

색깔이 같은 점끼리 사이클을 이루는지 확인하는 문제다.

방문하지 않은 점에서 DFS를 시작하자.
직전에 방문했던 점을 제외한 색깔이 같은 인접한 점으로 이동하면 되는데, 만약 이미 방문한 점이다? 그러면 사이클을 이루는 것이다.
이미 방문했던 점으로 다시 돌아갔다는 뜻이기 때문이다.

코드

• C++

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

typedef pair<int, int> pii;

const int MAXN = 50;

pii dir[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int n, m;
string board[MAXN];
bool visited[MAXN][MAXN];

bool dfs(int i, int j, int pi, int pj, char c){
    visited[i][j] = true;

    // 인접한 점 중 직전에 방문했던 점을 제외하고 색깔이 같은 점이 있으면 그곳으로 이동
    // 만약 이미 방문한 점이라면 사이클을 이룬다는 뜻
    for (auto [di, dj]: dir)
        if (0 <= i + di && i + di < n && 0 <= j + dj && j + dj < m && !(i + di == pi && j + dj == pj) && board[i + di][j + dj] == c)
            if (visited[i + di][j + dj] || dfs(i + di, j + dj, i, j, c))
                return true;
    return false;
}

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

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

    fill(&visited[0][0], &visited[n - 1][m], false);
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++){
        if (visited[i][j]) continue;
        if (dfs(i, j, -1, -1, board[i][j])){
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";
}

• Python

import sys; input = sys.stdin.readline
sys.setrecursionlimit(2500)

dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def dfs(i, j, pi, pj, c):
    visited[i][j] = True

    # 인접한 점 중 직전에 방문했던 점을 제외하고 색깔이 같은 점이 있으면 그곳으로 이동
    # 만약 이미 방문한 점이라면 사이클을 이룬다는 뜻
    for di, dj in dir:
        if 0 <= i + di < n and 0 <= j + dj < m and not (i + di == pi and j + dj == pj) and board[i + di][j + dj] == c:
            if visited[i + di][j + dj] or dfs(i + di, j + dj, i, j, c):
                return True
    return False

n, m = map(int, input().split())
board = [input().strip() for _ in range(n)]

visited = [[False] * m for _ in range(n)]
for i in range(n):
    for j in range(m):
        if visited[i][j]:
            continue
        if dfs(i, j, -1, -1, board[i][j]):
            print('Yes')
            exit()
print('No')