백준 10552번 DOM

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

추상적 그래프를 이용하여 풀어야했던 문제였습니다.(명시적으로 그래프가 주어지지 않았으므로 어떻게 그래프로 구현할까를 고민해보고 접근해야하는 문제였습니다.)

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

1. 싫어하는 채널을 인덱스로 두고 최고로 좋아하는 채널을 벡터에 추가해줍니다.

2. 큐에 현재 채널을 입력하고 현재 채널을 상영했다고 표시해줍니다.

3. 이후에는 BFS(Breadth First Search) 알고리즘처럼 접근하는데 최연소자만 움직여 채널을 바꿉니다.

i) 이미 해당 최연소자가 채널을 바꿨다면 사이클이 생성되었다는 것이므로 -1을 출력합니다.

ii) 해당 최연소자가 움직이지 않았다면 큐에 해당 최연소자가 좋아하는 채널을 넣고 바꾼 채널의 수를 1 증가시킵니다.

4. 해당 채널을 싫어하는 사람이 없을 경우 여태까지 바꾼 채널의 수를 출력해줍니다.

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

using namespace std;

 

const int MAX = 100000 + 1;

 

int N, M, P;

vector<int> graph[MAX];

bool visited[MAX];

 

int numOfChanges(void)

{

        queue<int> q;

        q.push(P);

        visited[P] = true;

 

        int cnt = 0;

        while (!q.empty())

        {

                 int cur = q.front();

                 q.pop();

 

                 //모든 사람이 해당 채널을 싫어하지 않는다면

                 if (!graph[cur].size())

                         return cnt;

                

                 //이미 해당 최연소자가 움직였을 경우

                 if (visited[graph[cur][0]])

                         break;

                 //해당 최연소자가 좋아하는 채널을 넣는다

                 q.push(graph[cur][0]);

                 visited[graph[cur][0]] = true;

                 cnt++;

        }

        return -1;

}

 

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> M >> P;

 

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

        {

                 int like, hate;

                 cin >> like >> hate;

 

                 graph[hate].push_back(like);

        }

 

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

        return 0;

}

개발환경:Visual Studio 2017

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