[Algorithm] 백준 16929 Two Dots - C++, DFS

16929번: Two Dots

#include <iostream>

using namespace std;

const int MAX = 51;

int n, m;
char map[MAX][MAX];
bool visit[MAX][MAX];
int moveX[] = { 0, 0, 1, -1 };
int moveY[] = { 1, -1, 0, 0 };

bool IsOut(int y, int x){
    if(y < 0 || x < 0 || y >= n || x >= m)
        return true;
    return false;
}

bool SearchCycle(int prevY, int prevX, int curY, int curX, const char color){
    if(visit[curY][curX])
        return true;
    
    visit[curY][curX] = true;

    for(int i = 0; i < 4; i++){
        int nextY = curY + moveY[i];
        int nextX = curX + moveX[i];

        if(IsOut(nextY, nextX))                 continue;
        if(map[nextY][nextX] != color)          continue;
        if(prevY == nextY && prevX == nextX)    continue;

        if(SearchCycle(curY, curX, nextY, nextX, color))
            return true;
    }
    return false;
}

int main(){
    // init
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // input
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> map[i][j];
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(visit[i][j]) continue;
            if(SearchCycle(-1, -1, i, j, map[i][j])){;
                cout << "Yes\n";
                return 0;
            }
        }
    }

    cout << "No\n";
    return 0;
}

---

"코테 전 가볍게 DFS 문제 풀어볼까" 하고 풀이한 문제인데 생각보다 자잘한 오류가 있어 시간이 좀 걸린 문제입니다.

 

위 로그들이 첫 만든 코드의 로그인데 큰 문제가 (1, 0)을 방문한 다음 다시 (1, 0)을 방문한 뒤 이걸 사이클로 판단하는게 문제였습니다. DFS 코드에서 이전에 간 곳을 체크하는 부분이 없어서 생기는 문제였습니다. 평소 문제라면 DFS 시작에서 visit = true 하고 끝날때 visit = false 를 해서 문제 풀이를 많이 했는데 이번 문제에서 visit 배열은 그런 용도로 사용된게 아니라 그런 방법은 사용할 수 없고 DFS 인자에서 '이전 지점' 을 전달해서 이 지점은 방문하지 않게 처리해주면 해결이 되었습니다.