완전탐색(유형정리) - 백준 1969

1969번: DNA (acmicpc.net)

1969번: DNA

 

DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오티드의 첫글자를 따서 표현한다. 만약에 Thymine-Adenine-Adenine-Cytosine-Thymine-Guanine-Cytosine-Cytosine-Guanine-Adenine-Thymine로 이루어진 DNA가 있다고 하면, “TAACTGCCGAT”로 표현할 수 있다. 그리고 Hamming Distance란 길이가 같은 두 DNA가 있을 때, 각 위치의 뉴클오티드 문자가 다른 것의 개수이다. 만약에 “AGCAT"와 ”GGAAT"는 첫 번째 글자와 세 번째 글자가 다르므로 Hamming Distance는 2이다.

우리가 할 일은 다음과 같다. N개의 길이 M인 DNA s1, s2, ..., sn가 주어져 있을 때 Hamming Distance의 합이 가장 작은 DNA s를 구하는 것이다. 즉, s와 s1의 Hamming Distance + s와 s2의 Hamming Distance + s와 s3의 Hamming Distance ... 의 합이 최소가 된다는 의미이다.

입력

첫 줄에 DNA의 수 N과 문자열의 길이 M이 주어진다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 DNA가 주어진다. N은 1,000보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다.

출력

첫째 줄에 Hamming Distance의 합이 가장 작은 DNA 를 출력하고, 둘째 줄에는 그 Hamming Distance의 합을 출력하시오. 그러한 DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다.

예제 입력 1 복사

5 8
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT

예제 출력 1 복사

TAAGATAC
7

예제 입력 2 복사

4 10
ACGTACGTAC
CCGTACGTAG
GCGTACGTAT
TCGTACGTAA

예제 출력 2 복사

ACGTACGTAA
6

예제 입력 3 복사

6 10
ATGTTACCAT
AAGTTACGAT
AACAAAGCAA
AAGTTACCTT
AAGTTACCAA
TACTTACCAA

예제 출력 3 복사

AAGTTACCAA
12

 

 

이전에 풀어본 문제이지만 거의 1년이 지나가니 문제가 거의 새로운 느낌이었다. 처음에 보면 문제를 이해하기 어려울 수 있는데, N개의 M개 뉴클레오타이드로 구성된 DNA구조를 입력받는다. 여기서 행렬의 느낌 or 이차원배열의 느낌이라는 것을 인식할 수 있다. 또한, 각 열마다 비교하여 가장 빈도가 많은 문자가 기준 문자가 된다. 이렇게 했을 때 대부분 기준문자로 이루어진 DNA구조가 Hamming Distance가 가장 작은 DNA가 될 것이라는 것을 파악할 수 있다. 여기서 우리는 완전탐색을 하면서 max 빈도수의 DNA를 구해야함을 알 수 있다. 그리고 마지막에 모든 DNA의 Hamming Distance의 합을 구하면 된다.

 

TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT

예제 1을 통해서 예시를 살펴보자.

 

열을 비교했을 때, 1열의 경우 T, 2열은 A, 3열은 A, 4열은 G, 5열은 A, 6열은 T, 7열은 A, 8열은 C가 가장 많은 빈도를 차지하는 문자라는 것을 알 수 있다. 여기서 이제 이 문자들을 제외한 값을 구해보면, 1,1,1,0,1,0,2,1이 되며 이 값을 모두 더하면 hamming distance인 정답 7이 됨을 파악할 수 있다.

 

이 원리를 그대로 코딩을 해보자.

 

N, M = map(int, input().split())

min_ham_d = ''
ham_count = 0
DNA = [input() for i in range(N)]


for i in range(M):               # M: 열
    DNA_idx = [0, 0, 0, 0]          # DNA_idx : DNA 빈도수
    for j in range(N):           # N: 행
        if DNA[j][i] == 'A':
            DNA_idx[0] += 1
        elif DNA[j][i] == 'C':
            DNA_idx[1] += 1
        elif DNA[j][i] == 'G':
            DNA_idx[2] += 1
        elif DNA[j][i] == 'T':
            DNA_idx[3] += 1

    max_idx = DNA_idx.index(max(DNA_idx))

    if max_idx == 0:
        min_ham_d += 'A'
    elif max_idx == 1:
        min_ham_d += 'C'
    elif max_idx == 2:
        min_ham_d += 'G'
    elif max_idx == 3:
        min_ham_d += 'T'

    ham_count += N - max(DNA_idx)

print(min_ham_d)
print(ham_count)

이렇게 해결할 수 있었다. 먼저 행, 열 문자 N과 M을 입력받고 새로운 반복리스트 DNA를 선언한다. 그 후 DNA_idx에 DNA의 빈도수를 채워넣는데 이 때, N행을 반복하면서 A,C,G,T의 경우를 모두 살펴보면서 DNA_idx 리스트에 빈도를 담아준다.

 

그 후 max_idx에 DNA_idx 리스트의 인덱스 중 큰 값을 담고 이 값을 0,1,2,3을 통해 조사, 가장 작은 hamming distance를 찾기 위한 변수에 A,C,G,T를 담아준다. 전체 변수 count를 위해 N값에 반복문 내에서 DNA_idx의 max 빈도수를 빼주고 카운트 해주면 가장 작은 hamming distance 정답을 찾아낼 수 있다. 

 

완전탐색의 느낌이 강하지만 그리디 알고리즘을 사용하면 더 빠르게 아이디어를 떠올릴 수 있을 것 같은 문제였다.