🖥️ CS/Baekjoon Algorithms

백준 16929번 Two Dots (C++)

한국의 메타몽 2021. 4. 13. 17:53

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

 

16929번: Two Dots

첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문

www.acmicpc.net

문제 풀이는 다음과 같다.

 

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;
}