백준 - 16929 Two Dots

문제 링크입니다 : https://www.acmicpc.net/problem/16929

16929번: Two Dots

 

사이클 찾는 유형이다.

 

사이클을 찾는 알고리즘은 DFS로 구현하는 것이 일반적이며

 

 

vector<vector<int>> adj;
vector<int> visiting;
vector<int> visited;

int findCircle(int here) {
	if (visiting[here]) return true;
	if (visited[here]) return false;
	visited[here] = true;
	visiting[here] = true;
	for (int i = 0; i < adj[here].size(); i++) {
		if (findCircle(adj[here][i])) return true;
	}
	visiting[here] = false;
	return false;
}

이런 코드를 미리 알고 있으면 매우 쉽게 해결할 수 있다.

 

 

 

 

#include <iostream>
#include <vector>


using namespace std;

const int dy[4] = {0, 0, -1, 1};
const int dx[4] = {-1, 1, 0, 0};

int N, M;
vector<vector<char>> board;
vector<vector<bool>> visited;
vector<vector<bool>> visiting;


bool findCircle(char color,int py, int px, int y, int x) {
    if(visiting[y][x]) return true;
    if(visited[y][x]) return false;
    visited[y][x] = true;
    visiting[y][x] = true;

    for(int dir = 0; dir < 4; dir++) {
        int ny = y + dy[dir];
        int nx = x + dx[dir];
        
        if(ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
        if(py == ny && px == nx) continue;
        if(board[ny][nx] != color) continue;
        if(findCircle(color, y, x, ny, nx)) return true;
    }
    visiting[y][x] = false;
    return false;
}

int main() {
    cin >> N >> M;

    board.assign(N, vector<char>(M));
    visited.assign(N, vector<bool>(M, false));
    visiting.assign(N, vector<bool>(M, false));

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> board[i][j];
        }
    }


    bool flag = false;

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
                if(findCircle(board[i][j], -1, -1, i, j)) {
                    flag = true;
                    break;
                }
            // }
        }
        if(flag) break;
    }

    if(flag) {
        cout << "Yes";
    } else {
        cout << "No";
    }

    return 0;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~