글 읽기 - 왜 맞았는지 모르겠습니다...

pv104 1년 전 0

제가 생각한 방법은 다음과 같습니다

1. 1~N까지 돌면서 스택에 초기값 i 세팅

2. DFS를 하면서 방문하지 않은 정점이라면 스택에 추가하고, 경로 저장용 큐에 추가

3. 다음에 갈 정점이 방문한 정점이라면 큐가 빌 때 까지 조건문 수행

3-1. 만약 큐의 첫번째 원소와 다음에 갈 정점이 같다면 싸이클이 있는 것이므로 해당 원소들은 모두 연결되었다고 생각하고 해당 원소들의 값을 -1로 변경

3-2. 다르다면 싸이클이 아니므로(=연결되지 않았으므로) 큐에서 제거

이 과정을 스택이 빌때까지 반복하는데, 그냥 생각나는대로 짜서 제대로 짠건지도 모르겠고 풀었는데 찝찝하네요...

궁금한 점은 두 가지입니다.

1. 제 코드는 이미 방문한 정점을 다시 방문하지 않는데, 방문한 정점을 다시 방문하지 않아도 정답이 될 수 있는건가요? 머리로 이해가 안 가네요..

2. 큐에 경로를 저장하는 방법 외에 다른 방법으로 경로를 저장할 수 있나요? 혹은 경로를 저장하지 않아도 풀 수 있는 방법이 있나요?

#include <iostream>
#include <stack>
#include <queue>
using namespace std;
#define MAX 100002
int board[MAX]; // 1부터
int t, n;
stack <int> s;
bool vis[MAX];
queue <int> q;
void input()
{
	fill(board, board + MAX, 0);
	fill(vis, vis + MAX, false);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> board[i];
	
}
int solve()
{
	for (int i = 1; i <= n; i++)
	{
		s.push(i);
		while (!s.empty())
		{
			int cur = s.top();
			s.pop();
			if (board[i] == -1) continue;

			if (vis[cur] == false) // 아직 방문하지 않은 경우:경로에 추가
			{
				vis[cur] = true;
				q.push(board[cur]);
				s.push(board[cur]);
			}
			else // 방문한 정점을 만나면: 추가된 경로 체크
			{
				while (!q.empty())
				{
					if (q.front() == board[cur]) // 다음 갈 정점과 큐의 맨 앞 원소가 같으면: 싸이클이 생성됨
												// 싸이클이 생성 된 그룹은 이미 한 팀으로 묶였으므로 -1 처리
					{							// 큐의 원소와 정점이 같지 않은 경우:싸이클이 아니므로 pop
						while (!q.empty())
						{
							board[q.front()] = -1;
							q.pop();
						}
						while (!s.empty())
						{
							s.pop();
						}
					}
					else
						q.pop();
				}
			}
		}
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++)
	{
		if (board[i] != -1) cnt++;
	}
	return cnt;
}
int main()
{
	cin.tie(0); ios::sync_with_stdio(0);
	cin >> t;
	while (t--)
	{
		input();
		cout << solve() << "\n";
	}
}

zenith82114 1년 전 1

1. 22~59줄 for문이 모든 정점에 대해서 도니까 모든 정점은 최소 1번 방문되고,

방문된 정점은 해당 for문이 끝나는 시점에

사이클에 속하는지 아닌지 판정이 되니까 괜찮아 보입니다.

2. 사이클을 찾아내려면 현재 경로에서 중복 방문된 점 "이후의" 점들을 알아야 하니

경로 기록을 안 할 수는 없을 텐데 다만 저라면 queue 말고 vector 쓸 것 같습니다.

굳이 앞에서 하나씩 빼지 않고 그냥 들어있는 채로 루프 돌려도 되니까요.

pv104 1년 전 0

@zenith82114 님 답변 감사드립니다!

1번은 저도 어느정도 이해가 되었습니다. 그런데 2번은 아직 이해가 가지 않는 부분이 있습니다

큐에서 원소를 빼면서 확인하지 않고 벡터로 확인한다면 어떻게 들어있는 채로 루프를 돌리게 되나요? find()함수를 이용해 벡터 안에서 찾는건가요?

zenith82114 1년 전 1

네, 맞습니다.

이미 방문했었던 점을 방문했다면 거기서 경로를 중단하고

현재 경로 안에서 그 점의 위치를 찾은 뒤

그 앞에 있는 원소들의 개수를 cnt에 더해주면 되겠죠.

아래는 제가 짜본 코드이고, 제출은 안 해봤지만 정답일 겁니다.

#include <iostream>
#include <algorithm> // find와 distance 함수
#include <vector>
using namespace std;
#define MAX 100002
int board[MAX];
bool vis[MAX];
int t, n;
void input()
{
	fill(board, board + MAX, 0);
	fill(vis, vis + MAX, false);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> board[i];
}
int solve()
{
    vector<int> path;
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        path.clear();
        int j = i;
        while (!vis[j]) {
            vis[j] = true;
            path.push_back(j);
            j = board[j];
        }
        // p부터 path의 끝까지가 사이클이 됨
        auto p = find(path.begin(), path.end(), j);
        // p보다 앞에 방문했던 점들은 사이클에 속하지 않음
        cnt += distance(path.begin(), p);
    }
    return cnt;
}
int main()
{
    cin.tie(0); ios::sync_with_stdio(0);
    cin >> t;
    while (t--)
    {
        input();
        cout << solve() << "\n";
    }
}

pv104 1년 전 0

@zenith82114 님 정말 감사합니다! 덕분에 이해했습니다 ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 맞았는지 모르겠습니다...

pv104 1년 전 0

zenith82114 1년 전 1

pv104 1년 전 0

zenith82114 1년 전 1

pv104 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말