백준 13023 - ABCDE

문제 설명

 

 

=> 그래프와 브루트 포스가 섞여 있는 문제입니다.

=> 자료구조 시간에 배운 그래프를 기억해내야 합니다.. 

=> 인접행렬, 인접 리스트, 간선 리스트 이 세 가지를 미리 만들어놓고 문제를 해결할 때 사용하면 좋습니다.

=> DFS, BFS 문제가 아니기 때문에 브루트포스 방식으로 문제를 풀어도 무방합니다.

 

 

 

 

 

=> 본인은 아래의 세가지 행렬과 리스트를 사용해서 문제 해결하였습니다.

bool arr[MAX][MAX]; //인접행렬
vector<int> list[MAX]; //인접리스트
vector<pair<int,int>>edges; //간선리스트

 

•  A -> B -> C -> D -> E 인 경로를 찾아야 한다. 

• A->B , B->C는 그냥 간선이기 때문에 간선 리스트로 찾는다. ( 이 경우, 브루트 포스를 사용하기 때문에 각 값들이 다른 값을 가리키는지 확인해주어야 한다.)

• B -> C는 인접 행렬로 찾을 수 있다. 

• D -> E는 인접 리스트로 찾을 수 있다. 

 

 

 

 

=> 위와 같은 방법으로 알고리즘을 짜보았습니다.

 

 

<code> 

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>


using namespace std;

#define MAX 2001

bool arr[MAX][MAX]; //인접행렬
vector<int> list[MAX]; //인접리스트
vector<pair<int,int>>edges; //간선리스트

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
  
    int N, M;
    cin >> N >> M;
    
    for(int i=0; i<M; i++)
    {
        int from,to;
        cin >> from >> to;
        edges.push_back({from, to});
        edges.push_back({to, from});
        arr[from][to] = arr[to][from] = true;
        list[from].push_back(to);
        list[to].push_back(from);
    }
    
    M*=2; //간선리스트 때문에 *2를 해주어야 한다. (인접리스트는 N에 해당)
    
    for(int i=0; i<M; i++)
    {
        for(int j=0; j<M; j++)
        {
            //A->B ,이미 간선으로 표현 가능
            int A=edges[i].first;
            int B=edges[i].second;
    
            //c->D
            int C = edges[j].first;
            int D = edges[j].second;
            
            if(A == B || A == C || A == D || B == C || B == D || C == D)
            {
                continue;
            }
            
            //B->C
            if(arr[B][C] == false) //case : B and C are not friends
            {
                continue;
            }
            
            //D -> E
            for(int E : list[D])
            {
                if(A == E || B == E || C == E || D == E)
                {
                    continue;
                }
                cout << 1<<'\n';
                return 0;
            }
    
        }
    }
    cout << 0 <<'\n';
    return 0;
}

 

 

실행 화면 1

 

실행 화면 2