BOJ 27558 - Find and Replace
그래프 애드혹 문제엔 성게 모양이나 $\rho$ 모양의 그래프를 이용한 성질이 단골 손님이다.
이 문제도 그런 류이다.
우선 $s=t$ 이면 정답은 $0$이다.
$t$가 $a-z,A-Z$ 까지 $52$개의 문자를 모두 포함하고 있다면 정답은 $-1$ 이다.
왜냐면 $s_i$ 를 $t_i$로 만들기 위해 어떤 $s_i$를 변환하는 순간 $s_i=s_j$ 인 것이 생기고, $s$에 있는 알파벳의 개수가 $t$에 있는 알파벳의 개수 $52$개보다 적어져서 불가능하다.
$s_i=s_j$ 인데 $t_i \ne t_j$ 인 경우가 있으면 정답은 $-1$이다.
왜냐면 $s_i$와 $s_j$는 항상 같이 바뀌어야 하기 때문에 $t$애서 다른 알파벳으로 귀결될 수 없기 때문이다.
그렇지 않다면 항상 가능하다.
$s_i \to t_i$ 라는 그래프의 간선을 만든다. 그럼 어떤 알파벳은 항상 $0$ 개 혹은 $1$ 개의 out 간선을 가진다.
그러면 각 연결 컴포넌트마다 최대 한개의 싸이클이 생긴다.
싸이클이 생기지 않으면 그 컴포넌트에서의 정답은 간선의 개수이다.
싸이클이 생기고 모든 정점이 그 싸이클에 포함되면 그 컴포넌트에서의 정답은 간선의 개수 + 1 이다.
왜냐면 모두 싸이클에 포함되면 어떤 알파벳을 싸이클에 포함되지 않는 다른 알파벳으로 바꿔두었다가 다른 것들을 처리한 뒤 다시 그 알파벳을 원래 바꿔야 했던 것으로 바꿔야 해서 한 번 더 과정이 포함된다.
$a \to b$와 $b \to a$ 를 보면, $a \to c$ 를 한 뒤에, $b \to a$를 하고 $c \to b$를 하면 세 번으로 변환이 가능함이 보인다.
어떤 연결 컴포넌트에서 싸이클이 생겼지만 싸이클에 포함되지 않는 간선이 있다면 정답은 간선 개수이다.
왜냐면 그런 상황이면 적어도 indegree가 2이상인 싸이클 내부의 정점 $u$이 존재한다는 의미이고, 싸이클 내부의 정점 $v$가 $v \to u$ 일 때, 싸이클 외부의 정점 $x$가 $x \to u$ 라고 한다면 $v \to x$로 바꿔주면 되기 때문이다.
여기서 $v \to x$ 를 하면,
이처럼 되어서 이제 싸이클이 없어져서 하나씩 처리해나가면 된다.
Comments