백준 2823번 유턴 싫어

문제

상근이는 여자친구와의 드라이브를 위해서 운전을 배우고 있다. 도로 연수를 10년쯤 하다 보니 운전은 그럭저럭 잘하게 되었다. 하지만, 그는 유턴을 하지 못한다. 10년동안 도로 연수를 받았지만 유턴을 하지 못한다. 밥먹고 유턴만 연습했지만, 결국 유턴은 하지 못했다.

상근이는 유턴을 연습하기 위해서 시간을 투자하는 대신에 유턴을 할 필요가 없고, 유턴이 금지된 마을로 이사가려고 한다.

상근이가 이사가려고 하는 마을은 막다른 길이 있으면 안 된다. 막다른 길은 유턴을 하지 않고는 빠져나올 수 없기 때문이다. 어떤 마을의 지도가 주어졌을 때, 유턴을 하지 않고 마을의 모든 구역을 돌아다닐 수 있는지 없는지(막다른 길이 있는지 없는지)를 구하는 프로그램을 작성하시오. 

마을의 지도는 R × C 칸으로 이루어진 표로 생각할 수 있다. 각 칸에 빌딩이 있다면 'X'로 표시하고, 길이라면 '.'으로 표시한다. 모든 칸은 빌딩 또는 길이다. 상근이가 어떤 길 위에 있다면, 근처 네 방향(위,아래,오른쪽,왼쪽)의 길로 이동할 수 있다. 빌딩으로는 이동할 수 없다.

이 마을에 막다른 길이 없다면, 상근이는 임의의 한 길에서 시작해서, 갈 수 있는 어떤 방향으로 움직이더라도, 유턴을 하지 않고 그 위치로 돌아올 수 있어야 한다. (유턴은 방향을 이동 방향이 180도로 바꾸는 것을 의미한다. 90도로 2번 바꾸는 것도 180도 이다)

입력

첫째 줄에 마을의 크기 R과 C가 주어진다. (3 ≤ R, C ≤ 10)

다음 R개 줄에는 마을의 지도가 주어진다. 모든 길은 서로 연결되어 있다. 또, 마을에는 적어도 두 개의 길이 있다.

출력

첫째 줄에 마을에 막다른 길이 없다면 0을, 그렇지 않다면 1을 출력한다.

 

 

 

런타임 에러가 발생하는 이유가 if문안에 범위 영역 조건과 벡터에서 탐색하는 것 전부 포함 했는데, 이러면 벡터(배열)내에 모든 원소를 다 돌 면서 영역에 포함 되는지와, X가 아닌  .인지를 같이 보는게 계속 발생하므로 런타임 에러가 발생한다. 미로와는 다른것은 미로는 queue에 들어간 인덱스에서만 빼서 보기 때문에 탐색이 그렇게 많지 않은데, 이거는 모든 원소를 다돌고 있으므로 안되는  것 같다. 영역에서 비교 후 벡터 원소를 보는 것에서 탐색시간이 줄어 드는 것이 맞으므로 런타임이 해결되었다. 앞으로 이런 문제에서는 구분 하기로 하자.  그 외 아이디어는 어떤 정점에서든 2개 이상의 통로가 있어야 사이클이 형성된다는 것. 어려운 문제였다. 

 

 

 

 

 

#include  <iostream>
#include  <string>

#include <vector>  

using namespace std;

 


int R, C;

vector <string> v;

 


 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> R >> C;

 

        v.resize(R);

        for (int i = 0; i < R; i++)

                 cin >> v[i];
                 
                 
        int cycle = false;

        for(int i=0; i<R; i++)

                 for (int j = 0; j < C; j++)

                 {

                         if (v[i][j] == 'X')

                                 continue;

 

                         int openPath = 0;

                         
                        if( 0 <= i+1 && i+1 < R && 0 <= j && j < C)
                        {
                         if(v[i+1][j] == '.')
                         openPath++;
}
 if( 0 <= i-1 && i-1 < R && 0 <= j && j < C)
                        {
                         if(v[i-1][j] == '.' )
                         openPath++;
}
 if( 0 <= i && i < R && 0 <= j+1 && j+1 < C)
                        {
                         if(v[i][j+1] == '.')
                         openPath++;
}
 if( 0 <= i && i < R && 0 <= j-1 && j-1 < C)
                        {
                         if(v[i][j-1] == '.')
                         openPath++;
}

                                                  
                         

 

                         //막다른 길

                         if (openPath <= 1)

                         {

                                 cycle = true;

                                 break;

                         }

                 }

 

       if(cycle)
       {
 cout << 1 << "\n";
}
else{
cout << 0 <<"\n";
}

        return 0;

}