JArchive 프로그래밍 일기

문제

Two Dots 백준 16929번

리뷰

처음에 BFS로 시도했는데, 문제의 에제 입출력 4개중에 3개만 맞아서 멘붕이 왔다.

3 4
AAAA
ABCA
AADA // 이건 사이클이 없는데. "Yes"를 출력한다... 

그래서 사이클 관련 질문게시판 글을 읽고 DFS로 시도해봤다.

시작지점을 목적지점 삼아서 탐색을 했다.

사이클은 시작점과 끝점이 같다고 생각할 수 있다.

그런데, 시작점 부터 방문 배열에 1로 체크해두면, 방문 안 해본 곳을 찾아서 탐색하기에는 시작점이자 끝점에 되돌아갈 수 없다. 그래서 이미 방문했더라도, 목적지인지 검사했다. 

일단 시작할 때 시작점 자체가 cnt 1개니까 1로 시작한다.

for(int i = 0; i  < N ; i++){  // 모든 지점에서 DFS 시작
    for(int j = 0; j < M ; j++){

        start_x = i; // 목적지 설정  
        start_y = j;

        DFS(i, j, 1); // 시작점에서 이미 cnt = 1 로 시작 

        if(stop_flag) break;
    }
} 

DFS를 시작하면, 방문 표시를 해두고, 상하좌우 4방향을 검사한다.

이 때, 아래의 3가지 조건을 만족하면 다음 칸으로 이동한다.

if(!boundary(next_x, next_y)) continue;  // 범위 내 인지  

if(B[start_x][start_y] != B[next_x][next_y]) continue; // 색깔이 같은지  

if(check[next_x][next_y] == 0){ // 미방문인지  

만약, 세번째 if 문에서 조건을 만족시키지 않고, 방문 했더라도, 목적지라면 탐색을 끝내야한다.

여기서 중요한 건 cnt가 4 이상인지도 함께 확인해야 한다는 것이다.

    if(check[next_x][next_y] == 0){ // 미방문인지  

        check[next_x][next_y] = 1;
        DFS(next_x, next_y, cnt+1); // 방문한다  
        check[next_x][next_y] = 0;

    }else{ // 목적지인지

        if(next_x == start_x && next_y == start_y && cnt >= 4){  // 4번 이상 움직여서 목적지 도달 
        stop_flag = true; // 탐색 끝!
        return;
    }
} 

맞는데 왜틀리지 ㅠㅠ 하고 골머리썩다가 BOJ 질문게시판에 글올려서 고수분들의 도움을 받았다. 정말 감사했다.

속시원했다.

코드

#include <iostream> 
#include <queue>
#include <algorithm>  
using namespace std;

int N, M;   // 행, 열  
char B[51][51]; //지도  
int check[51][51]; //방문 표시 지도

bool stop_flag = false;
int start_x, start_y; // 시작점을 '목적지'로 이용한다.  

// 4방향 
int dx[5] = {-1, 1, 0, 0}; 
int dy[5] = {0, 0, -1, 1};


// 지도 범위 내에 있는지 확인
bool boundary(int i, int j){   
    return (i >= 0 && i < N && j >= 0 && j < M) ? 1:0;
} 

void DFS(int now_x, int now_y, int cnt){ 

    if(stop_flag) return;

    check[now_x][now_y] = 1; // 방문  

    for(int i = 0; i<4; i++){ // 4방향 확인 

        int next_x = now_x + dx[i];
        int next_y = now_y + dy[i];

        if(!boundary(next_x, next_y)) continue;  // 범위 내 인지  

        if(B[start_x][start_y] != B[next_x][next_y]) continue; // 색깔이 같은지  

        if(check[next_x][next_y] == 0){ // 미방문인지  

            check[next_x][next_y] = 1;
            DFS(next_x, next_y, cnt+1); // 방문한다  
            check[next_x][next_y] = 0;

        }else{
            // 목적지인지  
            if(next_x == start_x && next_y == start_y && cnt >= 4){  // 4번 이상 움직여서 목적지 도달 
                stop_flag = true;
                return;
            }
        } 

    }

} 

int main(void){
     // freopen("input.txt", "rt", stdin);
     cin >> N >> M; 

    for(int i = 0; i <N; i++){
        for(int j = 0; j < M; j++){
            cin >> B[i][j];
        }
    }  // 입력받기 끝 

    string res = "";


    for(int i = 0; i  < N ; i++){  // 모든 지점에서 DFS 시작
        for(int j = 0; j < M ; j++){

            start_x = i; // 목적지 설정  
            start_y = j;

            DFS(i, j, 1); // 시작점에서 이미 cnt = 1 로 시작 

            if(stop_flag) break;
        }
    } 

    if(stop_flag) cout << "Yes";
    else cout << "No";

    return 0;    
}