백준 2671번
https://www.acmicpc.net/problem/2671
방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.
백준의 Contact문제와 거의 비슷한 문제이다.
정규표현식만 이해하고 있다면 어렵지않게 풀 수 있다.
문제에서 제공하는 패턴인
(100~1~|01)~ 과 Contact문제를 접합시키면 된다.
x~는 x가 한번 이상 반복되는 모든 소리의 집합을 말하고, (xyz)~는 괄호 안에 있는 xyz로 표현된 소리가 한번 이상 반복되는 모든 소리의 집합을 말한다.
라고 문제에서 되어있는데, 이 ~을 +로 바꾸기만 하면
그대로 정규표현식으로 사용할 수 있다.
import java.io.*; import java.util.regex.Pattern; public class Main { private static final Pattern P = Pattern.compile("(100+1+|01)+"); public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); System.out.println(P.matcher(br.readLine()).matches() ? "SUBMARINE" : "NOISE"); } // End of main } // End of class