[BOJ/백준] 16929 Two Dots

● [문제번호 16929] Two Dots

https://www.acmicpc.net/problem/16929

16929번: Two Dots

 

● 알아야 할 것

: DFS (재귀)

 

● 풀이 과정

: 문제를 읽고 첫번째로 생각난 풀이는

DFS (재귀)를 이용하여

모든 점을 시작점으로 확인하는데

사이클이 완성되는 경우는

시작점에서 최소 4개의 점을 방문하여 다시 시작점으로 돌아오는 것이다.

 

예제도 맞고 방문순서나 로직에는 문제가 없는 거 같지만

계속 1%에서 틀려서

(결국 틀리는 원인은 Yes, No를 YES, NO로 출력..)

구글링을 하다가 다른 관점으로 푼 풀이를 보았다.

 

사이클 생성!

 

방문한 점의 재귀 깊이의 차이를 계산해서 하는 풀이 인 것 같다.

그래서 사진에서 보는 것 같이

꼭 다시 시작점으로 돌아올 필요없이

탐색하다가 사이클이 만들어지면 바로 종료할 수 있어서

아마 내가 구현한 코드보다 더 빠를 것 같다.

 

: 내가 구현한 코드는

모든 점을 시작점으로 확인하고

사이클이 없다면 방문기록 초기화하고

다시 다음점을 시작점으로 확인하고

이러한 반복인데,

이 과정에서 불필요한 실행이 있긴하다.

 

● 주의 할 것

: Yes, No를 YES, NO로 출력하는 안타까운 일은 주의

 

: 시작점으로 돌아온 경우만 사이클로 인정되니

각 시작점을 실행한 후에

게임판 방문기록을 초기화해야한다.

 

● 참고 할 것

: 다른 관점으로 푼 풀이

https://kyu9341.github.io/algorithm/2020/02/17/algorithm16929/

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// controlX : 게임판에서 움직이기 위한 상, 하, 좌, 우
// controlY : 게임판에서 움직이기 위한 상, 하, 좌, 우
// dots : 게임판 저장
// visited : 게임판 방문기록
int controlX[4] = {-1, 1, 0, 0};
int controlY[4] = {0, 0, -1, 1};
char dots[51][51];
bool visited[51][51];
int N, M;

// 깊이 우선 탐색 (시작점Row, 시작점Col, 현재방문점Row, 현재방문점Col, 재귀깊이)
bool dfs(int startRow, int startCol, int fromRow, int fromCol, int cnt)
{
    visited[fromRow][fromCol] = true;
    
    for(int i = 0; i < 4; i++)
    {
        int row = fromRow + controlX[i];
        int col = fromCol + controlY[i];
        
        // 방문하면 안되는 4가지
        // 1. 게임판 X축을 벗어나는 경우
        if(row < 0 || N <= row)
            continue;
        // 2. 게임판 Y축을 벗어나는 경우
        else if(col < 0 || M <= col)
            continue;
        // 3. 다음점이 다른 색인 경우
        else if(dots[startRow][startCol] != dots[row][col])
            continue;
        // 방문했다면
        else if(visited[row][col])
        {
            // 시작점인 경우 → 사이클 확인 + 종료
            if(4 <= cnt && row == startRow && col == startCol)
                return true;
            // 4. 방문했지만 시작점이 아닌 경우
            continue;
        }
        else
        {
            // 사이클을 찾았다면 재귀 종료 반환
            if(dfs(startRow, startCol, row, col, cnt + 1))
                return true;
        }
    }
    
    // 사이클을 못 찾은 경우
    return false;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N >> M;
    
    // 게임판 저장
    for(int r = 0; r < N; r++)
        for(int c = 0; c < M; c++)
            cin >> dots[r][c];
    
    // 게임판의 모든 점을 시작점으로 확인
    for(int r = 0; r < N; r++)
    {
        for(int c = 0; c < M; c++)
        {
            // 게임판 방문기록 초기화
            fill(&visited[0][0], &visited[N][M], false);
            
            // 사이클을 찾은 경우 main문 종료
            if(dfs(r, c, r, c, 1))
            {
                cout << "Yes";
                return 0;
            }
        }
    }
    
    // 사이클을 못 찾은 경우
    cout << "No";
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [601 - 그래프 1 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	16929	Two Dots	https://pirateturtle.tistory.com/278
2	16947	서울 지하철 2호선	https://pirateturtle.tistory.com/279