[c++ | 백준] 18352번 특정 거리의 도시 찾기

c++ 문제 풀이

 

 

 

 

 

---

 

 

[백준 18352번 특정 거리의 도시 찾기 문제]

https://www.acmicpc.net/problem/18352

 

 

 

 

---

 

 

 

전체 풀이 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n, m, k, x;
vector<int> visited;
vector<int> result;
vector<vector<int>> v;

void BFS(int city)
{
    queue<int> q;
    q.push(city);
    visited[city] = 0;

    while (!q.empty())
    {
        int now = q.front();
        q.pop();

        for (int i = 0; i < v[now].size(); ++i)
        {
            if (v[now][i] == city) continue;

            if (visited[v[now][i]] == 0)
            {
                q.push(v[now][i]);
                visited[v[now][i]] = visited[now] + 1;
                if (visited[v[now][i]] == k)
                {
                    result.push_back(v[now][i]);
                }
            }
        }
    }
}

int main(void)
{
    int n1, n2;
    cin >> n >> m >> k >> x;
    v.resize(n + 1);
    visited.resize(n + 1);

    for (int i = 0; i < m; ++i)
    {
        cin >> n1 >> n2;
        v[n1].push_back(n2);
    }

    BFS(x);

    sort(result.begin(), result.end());

    if (result.empty())
        cout << -1;
    else
    {
        for (int var : result)
            cout << var << '\n';
    }

    return 0;
}

 

 

 

풀이 설명

 

1. 전역 변수

int n, m, k, x; // 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X
vector<int> visited; // 몇 번째로 방문한 곳인지 계산하기 위한 벡터
vector<int> result; // 결과로 출력할 도시를 담는 벡터
vector<vector<int>> v; // 입력받은 도시의 정보를 넣을 벡터

벡터 v에 도로의 정보를 넣어줄겁니다. 벡터 v를 이용하여 어떻게 문제를 풀 것 인지 설명드리도록 하겠습니다.

 

왼쪽 처럼 구성된 도시가 있다고 가정했을 때, 1번 도시는 2번, 3번 도시로 향하는 단방향 도로를 가지고 있습니다.

 

따라서 1번 인덱스에 2와 3을 넣어서 1번 도시가 어떤 도시를 갈 수 있는지를 표시해 주는 것 입니다.

 

 

 

이 방식으로 문제를 풀어보도록 하겠습니다.

다음으로 main 함수입니다.

 

 

2.  Main (초반 부분)

cin >> n >> m >> k >> x;
v.resize(n + 1);
visited.resize(n + 1);

for (int i = 0; i < m; ++i)
{
	cin >> n1 >> n2;
	v[n1].push_back(n2);
}

도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X를 입력받습니다. 그 후 도시의 개수에 따라 벡터들의 사이즈를 n+1로 resize합니다. n+1인 이유는 위에서 말씀드린 것 처럼 0번 도시는 존재하지 않기 때문에 0번 인덱스를 제외한 나머지(1~n) 인덱스를 사용하여 문제를 풀 것이기 때문입니다. 다음 for문을 통해 v에 입력을 받아 줍니다.

 

이제 BFS 함수를 설명드리도록 하겠습니다.

 

 

3. BFS

void BFS(int city)
{
    queue<int> q;
    q.push(city);
    visited[city] = 0;
    
    ...

출발 도시에서 최단 거리가 K인 도시들을 찾아내야 하기 때문에 매개변수로 출발 도시를 받습니다. 사실 X와 K는 전역 변수로 선언되어 있기 때문에 그냥 사용할 수 있지만 가독성을 위해서 X를 매개변수 city로 받아 함수를 실행하도록 하였습니다.

먼저 queue를 만들어 줄건데, 이제부터 q에 방문할 도시들은 차례로 담아 줄 겁니다. 먼저 출발 도시인 city를 q에 담아주고 출발 도시 부터 출발 도시 까지의 거리는 0이기 때문에 city의 visited값을 0으로 설정합니다.

 

while (!q.empty())
    {
        int now = q.front();
        q.pop();
        
        ...

q가 빌 때 까지 while문을 돌아줄겁니다. 먼저 q의 맨 앞에 있는 도시를 방문할 것이기 때문에 값을 now에 저장해준 뒤 pop을 통해 없애줍니다.

 

for (int i = 0; i < v[now].size(); ++i)
{
	if (v[now][i] == city) continue;
    
    ...
}

현재 방문한 도시와 연결 되어 있는 도시의 수 만큼 for문을 돌아줄겁니다. 만약 현재 방문한 도시와 연결되어 있는 도시가 출발 도시 라면 방문하면 안되므로 continue를 해줍니다.

 

 

...

if (visited[v[now][i]] == 0)
{
	q.push(v[now][i]);
	visited[v[now][i]] = visited[now] + 1;
	if (visited[v[now][i]] == k)
	{
		result.push_back(v[now][i]);
	}
}

for문 안에 있는 if문입니다.

지금 부터 현재 방문한 도시를 now, 현재 방문한 도시와 연결되어 있는 도시를 c라고 칭하겠습니다.

 

if문은 c를 방문 했었는지 판단하는 if문 입니다.

만약 방문하지 않았다면 q에 c를 넣어주고 c의 visited를 (now의 visited값 + 1)을 해줍니다.

그 이유를 그림을 통해 설명 드리도록 하겠습니다.

 

 

출발 도시는 1번 도시이며 1번 도시는 2번 도시,3번 도시를 방문할 수 있는 단방향 도로가 있습니다.

 

위의 now를1번 도시, c를 2와 3번 도시라고 생각해 봅시다.

 

현재 now의 visited는 0이고, c의 visited값은 now의 visited값 + 1이기때문에 0 + 1 = 1이 되는 것 입니다.

 

만약 2번 도시가 now이고 4번 도시가 c일때 c의 visited값은 어떻게 될까요?

정답은 1(c의 visited값) + 1 = 2입니다.

 

이렇게 visited값을 계속해서 구해 나가는 것입니다.

 

마지막 if문에서 구한 visited값이 k와 같으면 result벡터에 넣어주고 for문을 마칩니다.

 

---

 

 

그 뒤에 Main에서 result값을 sort로 정렬한뒤 출력해주면 됩니다.

긴 설명글을 봐주셔서 감사합니다.