백준 2671번 잠수함식별 [Java]

: ) YOUNG·2022년 4월 24일
2

알고리즘

목록 보기
111/417
post-thumbnail

문제

백준 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

0개의 댓글