백준 2823번 유턴 싫어

문제 링크입니다: https://www.acmicpc.net/problem/2823

처음에는 BFS 알고리즘으로 접근했다가 틀렸던 문제였습니다.

알고리즘은 아래와 같습니다.

1. 마을을 전부 탐색하는데 빌딩이면 지나가고, 길일 경우에만 상하좌우로 탐색합니다.

2. 길을 기준으로 상하좌우에 길이 없거나 길이 한군데에만 뚫려있을 경우 반드시 유턴을 해야합니다.

-> 따라서, 이런 케이스가 발생하면 사이클이 있다고 표시하고 반복문을 탈출합니다.

3. 사이클이 있을 경우 0, 없는 경우 1을 출력해줍니다.

#include <iostream>

#include <string>

#include <vector>

using namespace std;

 

typedef struct

{

        int y, x;

}Dir;

 

Dir moveDir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

 

int R, C;

vector<string> v;

 

int noUturn(void)

{

        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;

                         for (int k = 0; k < 4; k++)

                         {

                                 int nextY = i + moveDir[k].y;

                                 int nextX = j + moveDir[k].x;

 

                                 if (0 <= nextY && nextY < R && 0 <= nextX && nextX < C)

                                          if(v[nextY][nextX] == '.')

                                                  openPath++;

                         }

 

                         //막다른 길

                         if (openPath <= 1)

                         {

                                 cycle = true;

                                 break;

                         }

                 }

 

        return cycle ? 1 : 0;

}

 

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];

 

        cout << noUturn() << "\n";

        return 0;

}      

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~