[백준][C++] 16929 Two Dots

www.acmicpc.net/problem/16929

16929번: Two Dots

 

 

 

알고리즘 종류

    - 구현

    - BFS

 

 

 

사고 과정

    - 사이클을 형성하기 위하기 위한 조건

        * 시작점으로 돌아온다.

        * 최소 변의 개수가 4개이다.

 

    - 주변을 탐색하는 것이 아닌 깊이 우선 탐색하기 때문에 DFS를 사용한다.

    - 방문했던 곳을 확인하는 배열(isVisited)로 재방문을 하지 못하면 시작점에 도달할 수 없다. 그렇다고, 재방문을 허락하면, 무한히 순환한다. 그러면 시작점을 어떻게 방문할 수 있을까?

        * 시작점을 방문으로 체크되어 있다. 따라서 방문이 되었을 때는 무시하지 말고, 조건을 추가해 준다. 본인은 보통 아래와 같이 했었다.

        if(mat[cy][cx] != mat[ny][nx]) continue;
        if(!isValid(ny, nx)) continue;
        if(isVisited[ny][nx]) continue;

        * 아래와 같이 바꾼다. 

        if(mat[cy][cx] != mat[ny][nx]) continue;
        if(!isValid(ny, nx)) continue;
        if(isVisited[ny][nx]) continue;
        
        
        // 방문했던 곳인데  
        if(isVisited[ny][nx]) {
            // 그곳이 시작점이고 최소 4변으로 이루어져있으면 사이클이다. 
            if(ty==ny && tx==nx && cnt>=4){
                res = true;
                return;
            }
        }
        else{
            isVisited[ny][nx] = 1;
            // 방향이 다르면 변이 하나 생긴다. 
            if(cd!=d) dfs(ny, nx, d, cnt+1, ty, tx);
            else dfs(ny, nx, d, cnt, ty, tx);
        }

 

 

 

구현(C++)

#include <iostream>
#include <cstring>
 
using namespace std;
 
int w, h;
bool res=false;
 
char mat[51][51];
int isVisited[51][51];
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
 
 
bool isValid(int y, int x){
    return (y>=0 && y<h) && (x>=0 && x<w);
}
 
 
void dfs(int cy, int cx, int cd, int cnt, int ty, int tx){
    // 사이클이면 더 이상 DFS가 안 되도록 해야 한다. 
    if(res) return;
    
    for(int d=0; d<4; d++){
        int ny = cy + dir[d][0];
        int nx = cx + dir[d][1];
        
        if(!isValid(ny, nx)) continue;
        if(mat[cy][cx] != mat[ny][nx]) continue;
        
        // 방문했던 곳인데  
        if(isVisited[ny][nx]) {
            // 그곳이 시작점이고 최소 4변으로 이루어져있으면 사이클이다. 
            if(ty==ny && tx==nx && cnt>=4){
                res = true;
                return;
            }
        }
        else{
            isVisited[ny][nx] = 1;
            // 방향이 다르면 변이 하나 생긴다. 
            if(cd!=d) dfs(ny, nx, d, cnt+1, ty, tx);
            else dfs(ny, nx, d, cnt, ty, tx);
        }
    }
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> h >> w;
    
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> mat[i][j];
        }
    }
    
    // 시작점과 방향을 정해서 DFS 
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            for(int d=0; d<4; d++){
                memset(isVisited, 0, sizeof(isVisited));
                isVisited[i][j]=1;
                dfs(i, j, d, 1, i, j);
                if(res){
                    cout << "Yes" << endl;
                    return 0;
                }
            }
        }
    }
    
    cout << "No" << endl;
}

 

 

 

시행착오

    - 이전에 불 문제를 풀 때, 목적지에 도착하면 바로 빼야하는 것을 배웠다. 배우기 전에는 한 바퀴 돌려서 굳이 조건들을 한 번 더 거치게 해서 제출이 안 되었다. 이번에도 같은 문제였다. 저번과 다르게 시작점이다. 본인은 시작점의 방향을 설정하지 않고(-1을 매개변수로 넣음) DFS를 수행했다. 어차피 DFS에서 방향이 결정되기 때문이다. 테스트 케이스는 통과했지만 통과 못하는 케이스를 찾았다. 이를 방지하기 위해서는 시작할 때 방향을 미리 정하고 DFS를 수행하는 것이다. for문을 3개 사용했다. 괜히, 조금 더 단순하게 만들어 보려고 했더니, 알고리즘만 꼬였다. 정리 하자면, 시작 값 설정 그리고 목표값 도달에서는 쓸데없는 조건들을 거치게 하지 말자.

    // 시작점과 방향을 정해서 DFS 
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            for(int d=0; d<4; d++){
                memset(isVisited, 0, sizeof(isVisited));
                isVisited[i][j]=1;
                dfs(i, j, d, 1, i, j);
                if(res){
                    cout << "Yes" << endl;
                    return 0;
                }
            }
        }
    }

 

    - 이미 방문한 곳을 다시 방문해야 하는 문제였다. 처음 접하는 문제여서 어떻게 할 지 고민했다. 풀고 나니 재방문 조건을 추가하는 유형을 배울 수 있었다.