1304번 지역

문제 설명

이번 문제는 1~N의 도시에서 1->2, 2->3, i->i+1, N-1->N으로 가는 고속 도로가 있고 문제에서 일반 도로가 주어질 경우, 아래 조건을 만족하도록 지역을 나눌 경우 지역의 개수의 최대값을 구하는 문제입니다.

 

조건

• 지역 A의 어떤 도시에서 지역 B의 어떤 도시로 넘어갈 수 있는 경로가 있다면, B에 속해 있는 어떤 도시에서 A에 속해 있는 어떤 도시로 가는 경로는 없어야 합니다.
• 모든 지역의 도시 개수는 같아야 한다.

 

 

문제 풀이

아이디어 1

문제의 조건을 다시 생각해보기

위의 조건에 만족하도록 지역을 나눌 경우를 생각해보겠습니다.

모든 도시는 이미 자기보다 +1이 되는 도시로 향하는 도로가 하나씩 있다. 그렇다는 말은, 1에서 3으로 2에서 8로 X에서 Y(X<Y)으로는 이미 갈 수가 있다는 말입니다.

그러므로 조건에서 지역 A에서 지역 B로 갈 수 있지만 지역 B에서 지역 A로 갈 수 없다는 말은 A에 있는 모든 도시는 B의 도시보다는 숫자가 낮다는 것입니다!

 

이유

그 이유를 설명해보도록 하겠습니다.

N=8일 때, 1,2,3,5를 지역 A로 나누고, 4,6,7,8을 지역 B로 나누었을 경우를 생각해보면,

A의 어떤 도시 3에서 B의 모든 지역을 갈 수 있다. 하지만 B의 도시 4에서도 A의 도시 5를 갈 수 있으므로 위의 지역 나누기는 조건과 맞지 않습니다.

N=8일 때, 1,2,3,4를 지역 A로 나누고, 5,6,7,8을 지역 A로 나누었을 경우를 생각해보면,

A의 어떤 도시를 선택하더라도 B로 갈 수 있고, B의 어떤 도시를 선택하더라도 A로는 갈 수 없게 됩니다.

 

 

아이디어 2

입력된 일반도로에서 필요한 정보만 사용하기

주어진 일반도로는 S E와 같은 형태로 주어집니다.

우리는 S > E인 경우만 생각하면 됩니다.

 

이유

S < E인 경우는 생각할 필요가 없습니다. 왜냐하면, 이미 S < E인 경우라면 S도시에서 E도시로 갈 수 있기 때문입니다.

지역을 나눌 때 S와 E가 다른 지역으로 나뉜다면, S에서 E로 직접 연결된 일반도로가 없더라도 S에서 E는 갈 수 있고 E에서는 S를 가지 못하므로, 없어도 되는 조건입니다.

 

 

아이디어 3

유니온 파인드

여러 개의 도시를 지역으로 나눈다는 것은 하나의 뭉텅이로 묶는다는 것을 알 수 있습니다.

지역 A에서는 B를 갈 수 있으나 B에서는 A를 갈 수 없게 해야한다는 것은 A에서 B로 연결된 고속도로를 제외한 A와 B 서로를 연결하는 도로는 없다는 것을 알 수 있습니다. (있다고 하더라도 그것은 A에서 B로 연결된 일반도로 일 것입니다.)

즉, 입력된 일반 도로 S E (S>E인 경우)에서 E ~ S는 모두 같은 뭉텅이여야 합니다.

 

그리고, E ~ S는 한 뭉텅이라는 것을 표현하기 위해 모두 같은 부모를 가리키게 합니다.

 

이유

일반도로 입력으로 "5 1"이 주어졌을 경우 1,2,3,4가 지역 A가 되고 5,6,7,8이 지역 B로 한다면,

지역 A에서 B로 이동 가능하고 지역 B에서도 A로 이동 가능하기 때문에 불가능합니다.

 

위의 예시에서 1~5 사이에 있는 어떤 수라도 다른 지역이 된다면 문제의 조건에 맞지 않게 됩니다.

 

 

풀이

위의 아이디어 1, 2, 3를 생각하면서 문제를 풀어보도록 하겠습니다.

1. 입력된 일반도로 S E에서 S > E인 것들만 사용하도록 합니다.
2. 유니온 파인드를 이용해서 E~S사이에 있는 노드들의 부모를 모두 S의 부모로 지정해줍니다.
3. 1부터 N까지 for문을 통해 각 지역의 도시 개수를 지정해보고 문제의 조건에 맞는 경우를 찾습니다.

3. 추가 설명

N=12, 지역의 도시 개수가 3인 경우를 찾을 경우를 생각해보겠습니다.

아이디어 1에 의하면 나누어진 도시는 (1,2,3), (4,5,6), (7,8,9), (10,11,12)가 될 것입니다.

 

여기서 중요한 것은 3과 4, 6과 7 그리고 9와 10이 같은 부모를 두었는지 입니다.

같은 부모가 아니라면 각 지역은 모두 다른 뭉텅이가 될 것이고, 행여 지역 내부의 도시가 부모가 다르더라도 위 문제의 조건에는 모두 부합하기 때문에 해당 지역 나누기는 성공이라고 할 수 있습니다.

 

 

 

해결

이 문제는 유니온 파인드를 이용해 해결하면 되겠다는 생각은 일찍 했으나, 다른 규칙들을 생각해내는 것이 조금 오래 걸렸습니다.

저번에 풀어봤던 유니온 파인드를 복습할 수 있어 좋았습니다.

 

문제 링크 : https://www.acmicpc.net/problem/1304

1304번: 지역

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/1304.py