16947 서울 지하철 2호선

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

16947번: 서울 지하철 2호선

서울 지하철 2호선 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

512 MB

548

269

189

52.500%

문제

서울 지하철 2호선은 다음과 같이 생겼다.

지하철 2호선에는 51개의 역이 있고, 역과 역 사이를 연결하는 구간이 51개 있다. 즉, 정점이 51개이고, 양방향 간선이 51개인 그래프로 나타낼 수 있다. 2호선은 순환선 1개와 2개의 지선으로 이루어져 있다. 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고 한다. 지선은 순환선에 속하는 한 역에서 시작하는 트리 형태의 노선이다.

두 역(정점) 사이의 거리는 지나야 하는 구간(간선)의 개수이다. 역 A와 순환선 사이의 거리는 A와 순환선에 속하는 역 사이의 거리 중 최솟값이다.

지하철 2호선과 같은 형태의 노선도가 주어졌을 때, 각 역과 순환선 사이의 거리를 구해보자.

입력

첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호가 매겨져 있다. 임의의 두 역 사이에 경로가 항상 존재하는 노선만 입력으로 주어진다.

출력

총 N개의 정수를 출력한다. 1번 역과 순환선 사이의 거리, 2번 역과 순환선 사이의 거리, ..., N번 역과 순환선 사이의 거리를 공백으로 구분해 출력한다.

 

 

출처

• 문제를 번역한 사람: baekjoon

 

<개인풀이>

1. 순환선을 찾는다.

 - 어떻게 순환선을 찾을것인가?

  ( 방문하지 않은 정점을 방문시 간선 거리를 +1 추가, 간선거리가 1상태에서

     

    같은 지점을 방문하면 간선거리 유지, 이유는 1-2-1-2-1.. 방지하기위함

   

   -> 1-2-1-2 반복 방문은 순환선이 아님,

       하지만 1-2-3-1 은 간선거리가 2로 순환선이다.

     

2. 각 정거장 부터 순환선 까지의 거리를 구한다.

 

 

코드는 순환선들을 ans[] 배열에 1로 표시를 해놓고,

다시 dfs 방문을하여 1,2,3,4,5...,N 정류장부터 ans[]==1 인 녀석들과의

거리의 최소값을 출력한다.

 

#include<stdio.h>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
vector<int> v[3001];

bool check[3001];
int dist[3001];
int ans[3001]; //순환선 인덱스
int n; // 역의 갯수

void dfs(int node, int cnt);
void dfs2(int node, int cnt);
int main(void)
{
	int a, b;
	scanf("%d", &n);

	for (unsigned short i = 0; i < n;++i)
	{
		scanf("%d %d", &a, &b);
		v[a].push_back(b);
		v[b].push_back(a);
	}

	for (unsigned short i = 1; i <= n; ++i)
	{
		dfs(i, 0);
		memset(check, false, sizeof(check));
		memset(dist, 0, sizeof(dist));
	}

	for (unsigned short i = 1; i <= n; ++i)
	{
		dfs2(i, 0);
		int min = 3001;
		for (unsigned short k = 1; k <= n; ++k)
		{
			if (ans[k])
			{
				if (min > dist[k])
					min = dist[k];
			}
		}
		printf("%d ", min);
		memset(check, false, sizeof(check));
		memset(dist, 0, sizeof(dist));
	}
	return 0;
}


void dfs2(int node, int cnt)
{
	check[node] = true;
	dist[node] = cnt;
	for (unsigned short i = 0; i < v[node].size(); ++i)
	{
		int temp = v[node][i];
		if (check[temp] == 0)
		{
			dfs(temp, cnt + 1);
		}
	}
}

void dfs(int node, int cnt)
{
	if (check[node])//이미 방문했던곳,
	{
		//해당 노드가 순환선,
		if (cnt - dist[node] >= 2)
		{
			ans[node] = 1;
			return;
		}
		else
		{
			return;
		}
		
	}
	
	check[node] = true;
	dist[node] = cnt;
	for (unsigned short i = 0; i < v[node].size(); ++i)
	{
		int temp = v[node][i];
		
		if (check[temp]==0)
		{
			dfs(temp, cnt+1);
		}
		else dfs(temp, cnt);
		
	}
}