BOJ-1013 Contact Swift

문제

“무한히 넓은 저 우주에 인류만이 홀로 존재한다면, 그건 정말 슬픈 일이 아닐까요”

푸에르토리코 아레시보에 위치한 아레시보 전파망원경(Arecibo radio telescope)은 수십 년째 존재하지 않을 지도 모르는 외계 문명으로부터의 전파를 수신하기 위해 밤하늘을 바라보고 있다.

이 망원경이 수집한 전파 속에서 자연적으로 발생하기 힘든 패턴들을 찾아내어, 그것을 증거로 외계 문명의 존재 여부를 가리려는 노력은 줄곧 이어져왔지만 아직까지도 그러한 패턴은 발견되지 않았다. 한국 천문학계의 자존심 김동혁 박사는 국내 기술로 이러한 탐사를 진행하기 위하여 다음의 전파 표기를 표준으로 삼았다.

전파의 기본 단위는 { 0 , 1 } 두 가지로 구성되어있으며, x+ ( ) 는 임의의 개수(최소 1개) x의 반복으로 이루어진 전파의 집합을 나타낸다.

(xyx)+ ( ) 는 괄호 내의 xyx의 반복으로 이루어진 전파의 집합을 뜻한다. 아래는 이해를 돕기 위한 예제이다.

• 1+ = { 1, 11, 111, 1111, 11111, … }
• 10+ = { 10, 100, 1000, 10000, 100000, … }
• (01)+ = { 01, 0101, 010101, 01010101, 0101010101, … }
• (1001)+ = { 1001, 10011001, 100110011001, … }
• 10+11 = { 1011, 10011, 100011, 1000011, 10000011, … }
• (10+1)+ = { 101, 1001, 10001, 1011001, 1001101, 100011011000001, … }

반복을 의미하는 + 외에도 or 를 의미하는 | 기호가 있다. { x | y } 는 x 혹은 y 를 의미하는 것으로, { 0+ | 1+ } 는 { 0 , 1 , 00 , 11 , 000 , 111 , … } 의 집합을 의미한다. 아래는 두 기호를 복합적으로 사용한 예이다.

• (100 | 11)+ = { 100 , 11 , 10011 , 11100 , 1110011100 , 100111111100100, … }

최근 김동혁 박사는 아레시보 전파망원경에서 star Vega(직녀성) 으로부터 수신한 전파 기록의 일부를 조사하여 그 전파들의 패턴을 분석하여 아래와 같이 기록하였다.

• (100+1+ | 01)+

김동혁 박사는 다양한 전파 기록 중에서 위의 패턴을 지니는 전파를 가려내는 프로그램을 필요로 한다. 이를 수행할 수 있는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ N ≤ 200)의 범위를 갖는다.

출력

각 테스트 케이스에 대해 주어진 전파가 문제에서 제시한 패턴이면 “YES”를 그렇지 않은 경우는 “NO”를 출력한다. 출력 문자열은 모두 대문자로 구성되어 있다.

내가 푼 풀이

- 처음엔 그리디기법으로 입력받는수 100, 01 에따라 다음에 올 수 있는 수들만 넣었더니 틀렸다.

- 그리디로 하니까 반례들이 너무많았고 정확히 답을 구할 수 없었다.

- 다른사람의 풀이를 참고해봤는데, 다양하게 풀이 방법이 있었다..

- 이 문제는 완전탐색 dfs를 이용했지만 조건을맞춰서 탐색하였다.

 

맨처음에 올수있는 문자는 100혹은 01이다.

100이 온다면 0, 1이 올 수 있다

01이 온다면 다시 100이 오거나, 01이 올 수 있다.

100다음에 0이 온다면 0또는 1이 올수있다 이는 위의 100이 왔을때의 조건과 같다.

100다음에 1이 온다면 1 또는 01 또는 100이 올 수 있다.

이렇게 각각 문자간의 관계가 형성되는데, 관계만 따지고 다음에 올 수 있는 모든 경우의 수를 탐색한다면 시간초과가 날 것이다.

조건을 더 추가해서, 앞의 문자를 미리 받고 해당문자와 이전문자의 관계있는문자가 동일하다면 탐색하는 방향으로 지었다.

 

예) 100101

1. 첫번째 올 수 있는 문자: [100, 01] , 앞의 문자 스캔: 100 , 10

100이 동일하므로 100 배치 -> 100

 

2. 100다음에 올 수 있는문자: [0,1] , 앞의 문자 스캔 1

1이 동일하므로 1 배치 -> 1001

 

3. 1다음에 올 수 있는문자: [1, 01, 100] , 앞의 문자 스캔 [0, 01, 01x]

01이 동일하므로 01 배치 -> 100101 결과 YES

 

코드로 구현하면 다음과 같다.

 

import Foundation

// 문자 해당 범위를 출력하기위해 별도의 메서드 생성
// 문자를 받는중 주어진 문자열을 초과한다면 임의의 문자(여기선 2)를 더 붙여준다.
extension String {
    func getRangeString(start: Int, end: Int, max: Int) -> String {
        var result = ""
        for i in start...end {
            if i >= max {
                result += "2"
            } else {
                result += "\(self[self.index(startIndex, offsetBy: i)])"
            }
        }
        return result
    }
}

// 테스트케이스 수
let T = Int(readLine()!)!
var result = String()

// dfs
func dfs(str: String, targetStr: String, count: Int, compare: String) {
    var target = targetStr
    // 찾는도중에 이미 찾았거나, 찾는범위가 주어진 문자열을 넘어버린경우 종료
    if result == "YES" || count > target.count {
        return
    }
    // 배치한 문자가 주어진 문자열과 동일하다면 YES
    // 하지만 마지막문자가 100으로 끝난다면 주어진 규칙과 맞지않는다.
    if str == target && compare != "100" {
        result = "YES"
        return
    }
    
    // 이전 문자와의 관계에 따라서 다음에 올 문자를 찾는다.
    // 맨 처음시작할때나 이전문자가 01 일때 올수있는문자 100, 01
    if compare == "" {
        var s1 = ""
        var s2 = ""
        
        //뒤의문자를 탐색
        if count+2 <= target.count {
            s1 = target.getRangeString(start: count, end: count+2, max: target.count)
        }
        if count+1 < target.count {
            s2 = target.getRangeString(start: count, end: count+1, max: target.count)
        }
        
        //앞의문자와 그다음 올수있는문자가 동일하다면 추가
        if s1 == "100" {
            dfs(str: str + "100", targetStr: target, count: count+3, compare: "100")
        }
        if s2 == "01" {
            dfs(str: str + "01", targetStr: target, count: count+2, compare: "")
        }
    } else if compare == "100" {
        // 이전문자가 100일때, 올수있는문자 0,1
        var s = ""
        
        //뒤의문자 탐색
        if count+1 <= target.count {
            s = target.getRangeString(start: count, end: count, max: target.count)
        }
        
        //뒤의문자와 그다음 올수있는문자가 동일하다면 추가
        if s == "1" {
            dfs(str: str + "1", targetStr: target, count: count+1, compare: "1")
        }
        if s == "0" {
            dfs(str: str + "0", targetStr: target, count: count+1, compare: "100")
        }
    } else if compare == "1" {
        // 이전문자가 1일때, 올수있는문자 100, 01, 1
        var s1 = ""
        var s2 = ""
        var s3 = ""
        
        //뒤의 문자 탐색
        if count <= target.count {
            s1 = target.getRangeString(start: count, end: count, max: target.count)
        }
        if count + 1 <= target.count {
            s2 = target.getRangeString(start: count, end: count+1, max: target.count)
        }
        if count + 2 <= target.count {
            s3 = target.getRangeString(start: count, end: count+2, max: target.count)
        }
        
        //뒤의문자와 그다음 올수있는문자가 동일하다면 추가
        if s1 == "1" {
            dfs(str: str + "1", targetStr: target, count: count+1, compare: "1")
        }
        if s2 == "01" {
            dfs(str: str + "01", targetStr: target, count: count+2, compare: "")
        }
        if s3 == "100" {
            dfs(str: str + "100", targetStr: target, count: count+3, compare: "100")
        }
    }
    
}
for i in 0..<T {
    result = "NO"
    var target = readLine()!
    dfs(str: "", targetStr: target, count: 0, compare: "")
    print(result)
}