[코드포스 Practice16] C. Strongly Connected City

아니! 이게 무슨 문제람!

머람!

코드포스 문제 인간적으로 내라 좀!

 

막 고민하다가 처음에는 규칙이 있나 싶어서

이렇게 빙글빙글 돌게끔 만들어야 하는 줄 알았다. 

하지만 아무리 생각해서 근거없고 규칙도 잘 모르겠고 해서 직접 경로를 다 찾아서 해결하려 했다. 

 

먼저 교차로를 배열로 만든다. 

다음으로 [0,0] -> [0,1] ... -> [2,2]까지 출발지점을 이동하면서 해당 출발지점 일 때 갈 수 있는 곳을 1로 체크한다.

만약 0이 있다면 그건 갈 수 없는 곳이 있다는 뜻이므로 "NO" 출력하고 종료.

 

1로 체크하는 함수 짜는게 제일 힘들고 시간 많이 걸렸음.. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
 
using namespace std;
using i64 = long long;
 
void left_to_right(vector < vector <int> > &v, int x, int y, int m)
{
    for (int i = y; i < m; i++)
    {
        v[x][i] = 1;
    }
}
 
void right_to_left(vector < vector <int> > &v, int x, int y)
{
    for (int i = 0; i <= y; i++)
    {
        v[x][i] = 1;
    }
}
 
void up_to_down(vector < vector <int> > &v, int x, int y, int n)
{
    for (int i = x; i < n; i++)
    {
        v[i][y] = 1;
    }
}
 
void down_to_up(vector < vector <int> > &v, int x, int y)
{
    for (int i = 0; i <= x; i++)
    {
        v[i][y] = 1;
    }
}
 
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    string row, col;
    cin >> row >> col;
    
    bool is_ok = true;
    
    for (int x = 0; x < n; x++)
    {
        for (int y = 0; y < m; y++)
        {
            vector<vector<int> > v(n, vector<int>(m, 0));
            v[x][y] = 1;
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    if (v[i][j] == 1)
                    {
                        
                        if (row[i] == '>')
                            left_to_right(v, i, j, m);
                        else if (row[i] == '<')
                            right_to_left(v, i, j);
                        if (col[j] == 'v')
                            up_to_down(v, i, j, n);
                        else if (col[j] == '^')
                            down_to_up(v, i, j);
                        else
                            cout << "여기에러" << endl;
                    }
                }
            }
            // cout << "----------------" << endl;
            // for (int i = 0; i < n; i++)
            // {
            //     for (int j = 0; j < m; j++)
            //     {
            //         cout << v[i][j] << " ";
            //     }
            //     cout << endl;
            // }
            
            //0이 있는 지 확인
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    if (v[i][j] == 0)
                    {
                        cout << "NO";
                        return 0;
                    }
                }
            }
        }
    }  
    cout << "YES";
    
    return 0;
}

 

아무튼 이렇게 하면 맞을 줄 알았는데 두 번째 예제에서 틀렸다. 

 

 

주석을 없애고 첫 번째 예제를 돌려보면 이렇게 나온다. 

이거 대회 중에는 몰랐는데 지금 확인해보니 어쩌다 답이 맞은 거였군..

 

암튼 다시 넘어가서 두번째 예제..

 

YES가 나와야하는데 NO가 나왔다

 

내 생각에는 반복문이 

->

->

->

이런 순서로 확인하다가 빠진 부분이 있는 것 같다. 

그래서 이걸 두 번정도 확인해야하나? 생각이 들었는데 그럼 출발 지점이랑 상관 없이 확인하는 거 아닌가... 음...

 

뭔가 트리로 길 쭉쭉 따라가다 돌아오는 그런게 떠오르긴 하는데 잘 모르겠다. 

 

---

 

트리..! 맞았다. 

알고보니 이 문제는 탐색 문제였다. 

BFS나 DFS 들어나 봤지 어떻게 구현하는지 몰랐는데 이 기회에 공부해야겠다. 

 

https://burningjeong.tistory.com/208

DFS 깊이 우선 탐색

 

너무 낯설다!

하지만 익숙해져야겠지

 

아무튼 저 코드 참고해서 구현했다.

 

 

다른 점이라면 이 문제는 방향 그래프이므로 노드 연결하는데 좀 주의해야했다.

여담이지만 노드 번호붙이는게 제일 힘들었음ㅋㅋ 특히 세로ㅜㅜㅜㅜ j + (m * j) 이거 숫자 계산 너무 복잡함..

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
 
using namespace std;
using i64 = long long;

class Graph {
public:
    int N;
    vector<vector <int>> adj;
    vector<bool> visited;
    
    Graph() : N(0) {}
    Graph(int n) : N(n) {
        adj.resize(N);
        visited.resize(N);
    }
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }
    
    void sortList() {
        for (int i = 0; i < N; i++)
        {
            for (int i = 0; i < N; i++)
                sort(adj[i].begin(), adj[i].end());
        }
    }
    
    int dfsAll(int start)
    {
        int components = 0;
        fill(visited.begin(), visited.end(), false);
        
        for (int i = 0; i < N; i++)
        {
            if (start >= N)
                start = 0;
            if (!visited[start])
            {
                //cout << "new DFS begin" << endl;
                dfs(start++);
                components++;
            }
        }
        
        return components;
    }
    
    void dfs()
    {
        fill(visited.begin(), visited.end(), false);
        dfs(0);
    }
private:
    void dfs(int curr)
    {
        visited[curr] = true;
        //cout << "node " << curr << " visited " << endl;
        for (int next: adj[curr])
            if (!visited[next]) dfs(next);
    }
};
 
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    string row, col;
    cin >> row >> col;
    
    Graph G(n*m);
    //<><>부터 edge 연결
    for (int j = 0; j < n; j++)
    {
        if (row[j] == '>')
        {
            for (int i = 0; i < m-1; i++)
            {
                G.addEdge((m*j) + i, (m*j) + i+1);
            }
        }
        else
        {
            for (int i = m-1; i > 0; i--)
            {
                G.addEdge((m*j) + i, (m*j) + i-1);
            }
        }
    }
    
    //v^v edge 연결
    for (int j = 0; j < m; j++)
    {
        if (col[j] == 'v')
        {
            for (int i = 0; i < n-1; i++)
            {
                G.addEdge(j + m*i, j + m*(i+1));
            }
        }
        else
        {
            for (int i = n-1; i > 0; i--)
            {
                G.addEdge(j + m*i, j + m*(i-1));
            }
        }
    }
    
    G.sortList();
    for (int i = 0; i < n*m; i++)
    {
        int result = G.dfsAll(i);
        if (result != 1)
        {
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";
    return 0;
}

 

이 문제에서 시작점을 달리해서 총 몇개의 그래프로 나뉘는지 봐야 하므로 dfsAll을 쓰고 시작점을 따로 명시해줬다. 

 

힘들었다... 후...