[백준] 16929번 : Two Dots

문제

 

---

풀이

 

myunji.tistory.com/350

[백준] 4803번 : 트리

이 문제에서 사이클을 찾는 방법을 배웠다.

 

이번에도 똑같은 방법으로 dfs를 하면서 사이클을 찾으면 된다.

그냥 사이클 여부만 확인하면 되는거라 간단한 문제다.

---

소스코드

 

#include <iostream>
#include <vector>
#include <utility>
#include <string>

using namespace std;

vector<vector<pair<char, bool>>> board; //문자, 방문여부
int N, M;
bool isCycle;
pair<int, int> dir[4] = {{-1, 0},  //상
                         {1,  0},  //하
                         {0,  -1}, //좌
                         {0,  1}}; //우

void dfs(pair<int, int> cur, pair<int, int> source) { //cur=이번에 탐색할 좌표, source=cur의 이전 좌표
    int row = cur.first;
    int col = cur.second;

    if (board[row][col].second) { //이미 방문했던 좌표면 사이클이 형성된 것
        isCycle = true;
        return;
    }
    board[row][col].second = true; //방문처리
    for (int i = 0; i < 4 && !isCycle; i++) { //상하좌우 확인
        int nr = row + dir[i].first;
        int nc = col + dir[i].second;
        if ((nr >= 0) && (nr < N) && (nc >= 0) && (nc < M) && //범위 체크
            (board[row][col].first == board[nr][nc].first) && //같은 문자 확인
            ((nr != source.first) || (nc != source.second))) { //source 좌표가 아닌지 확인
            dfs(make_pair(nr, nc), cur);
        }
    }
}

int main() {
    string input;

    cin >> N >> M;
    board.assign(N, vector<pair<char, bool>>(M));
    for (int i = 0; i < N; i++) {
        cin >> input;
        for (int j = 0; j < M; j++) {
            board[i][j].first = input[j];
            board[i][j].second = false;
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!board[i][j].second) { //미방문 좌표
                dfs(make_pair(i, j), make_pair(-1, -1));
                if (isCycle) { //사이클 있음
                    cout << "Yes\n";
                    return 0;
                }
            }
        }
    }
    cout << "No\n"; //사이클 없음
}

전체 소스코드다.

 

vector<vector<pair<char, bool>>> board; //문자, 방문여부
int N, M;
bool isCycle;
pair<int, int> dir[4] = {{-1, 0},  //상
                         {1,  0},  //하
                         {0,  -1}, //좌
                         {0,  1}}; //우

isCycle 변수로 사이클이 하나라도 나왔는지 확인하고

board 2차원 벡터에는 pair를 넣어 특정 위치의 문자와 방문 여부를 저장했다.

 

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!board[i][j].second) { //미방문 좌표
                dfs(make_pair(i, j), make_pair(-1, -1));
                if (isCycle) { //사이클 있음
                    cout << "Yes\n";
                    return 0;
                }
            }
        }
    }

게임판의 모든 방문하지 않은 좌표에 대해 dfs를 한다. 인접하고 같은 문자인 모든 좌표가 방문처리 된다.

 

void dfs(pair<int, int> cur, pair<int, int> source) { //cur=이번에 탐색할 좌표, source=cur의 이전 좌표
    int row = cur.first;
    int col = cur.second;

    if (board[row][col].second) { //이미 방문했던 좌표면 사이클이 형성된 것
        isCycle = true;
        return;
    }
    board[row][col].second = true; //방문처리
    for (int i = 0; i < 4 && !isCycle; i++) { //상하좌우 확인
        int nr = row + dir[i].first;
        int nc = col + dir[i].second;
        if ((nr >= 0) && (nr < N) && (nc >= 0) && (nc < M) && //범위 체크
            (board[row][col].first == board[nr][nc].first) && //같은 문자 확인
            ((nr != source.first) || (nc != source.second))) { //source 좌표가 아닌지 확인
            dfs(make_pair(nr, nc), cur);
        }
    }
}

이건 4803번에서 사용한 코드와 거의 유사하다.

그래프의 표현 방식만 달라진 것이다.