백준 16929번 Two Dots (C++)

문제 링크 : www.acmicpc.net/problem/16929

16929번: Two Dots

문제 풀이는 다음과 같다.

 

1. 2차원 배열을 입력받는다.

2. 배열의 첫 지점부터 끝지점까지 2중 for문을 돌린다. 만약 해당 지점을 방문한 적이 없으면 dfs를 시작한다. 

dfs로 넘겨받는 인자는 다음 세개이다.

(1) x좌표 (2) y좌표 (3) 지금까지 거쳐온 지점의 갯수

또한 이때 주의해야할 점이 있다.

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(!ch[i][j]){
                sy = i, sx = j;
                dfs(i,j,1);
                ch[i][j] = true;
            }
        }
    }

sy, sx는 시작지점을 의미한다. 시작지점을 별도로 저장해야하는데, 결국 dots게임에서 성공하려면 여러지점을 돌고 최초의 지점으로 되돌아와야하기 때문이다. 또한, 첫 스타트 지점을 다시 방문할 필요는 없으므로, 반드시 dfs를 종료하고 방문했다는 흔적을 남겨야한다.

3. 먼저 dfs로 넘겨받은 위치를 방문 표시 해준다. 

해당 지점의 4방위로 if문 체크를 한다. if체크는 다음과 같다.

    ch[y][x] = true; // 방문 체크
    for(int i=0; i<4; i++){
        ny = y+my[i];
        nx = x+mx[i];
        if(ny>=0&&ny<n&&nx>=0&&nx<m&&v[y][x]==v[ny][nx]&&!ch[ny][nx]) dfs(ny,nx,num+1);
        else if(sy==ny&&sx==nx&&num>=4){
            cout << "Yes" << "\n";
            exit(0);
        }
    }
    ch[y][x] = false; // 방문 해제

if문은 해당 지점이 범위를 초과하지 않았으며, 동시에 같은 글자이며 아직 방문한 적이 없다면 dfs를 진행한다. 이때 방문횟수는 +1을 해준다.

else if문은 만약 해당 지점이 스타트 지점과 동일하며, 방문 지점이 4이상이라면 Yes를 출력하고 종료한다.

4. 모든 지점을 검사해도 Yes가 나오지 못했다면 No를 출력한다.

 

#include <iostream>
#include <vector>
#define MAX 51
using namespace std;

bool ch[MAX][MAX];
int n,m,sy,sx,my[] = {0,0,1,-1}, mx[] = {1,-1,0,0}, ny, nx;
vector<vector<char>> v(50,vector<char>(50,0));

void dfs(int y, int x, int num){
    ch[y][x] = true;
    for(int i=0; i<4; i++){
        ny = y+my[i];
        nx = x+mx[i];
        if(ny>=0&&ny<n&&nx>=0&&nx<m&&v[y][x]==v[ny][nx]&&!ch[ny][nx]) dfs(ny,nx,num+1);
        else if(sy==ny&&sx==nx&&num>=4){
            cout << "Yes" << "\n";
            exit(0);
        }
    }
    ch[y][x] = false;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> v[i][j];
            ch[i][j] = false;
        }
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(!ch[i][j]){
                sy = i, sx = j;
                dfs(i,j,1);
                ch[i][j] = true;
            }
        }
    }
    cout << "No" << "\n";
    return 0;
}