[BOJ/1062/Golang] 백준 1062 - 가르침

백준 1062 - 가르침 [Gold/4] - Golang

사족

훈련소에서 백준 랭킹 1위인 구사과님을 만났습니다. 엄청난 우연이었는데, 이 때 많은걸 배운 것 같습니다.

앞으로는 제가 풀었던 문제들, 한참 생각해보았지만 떠오르지 않아 인터넷을 조금 참조 또는 대다수 참조한 경우 가리지 않고 생각의 흐름과 이해한 내용을 정리해서 포스팅할 계획입니다. 두서가 없고 설명이 어색한 때가 있으면 가감없이 댓글로 남겨주시면 감사하겠습니다 🙂

접근 방식

주어진 N, K, 단어의 길이가 브루트포스한 완전 탐색을 수행할 수 있을 정도의 크기라서 완전 탐색을 사용하기로 했습니다.

처음에는 단어를 순회하면서 가장 최적의 알파벳을 찾아야 하는 것인 줄 알았는데, 알파벳을 사용할 수 있는만큼 뽑고, 해당 알파벳 집합으로 주어진 단어를 순회했을 때 몇 개의 단어를 이해할 수 있는지 탐색하는 문제였습니다.

순서

1. 우선 'a', 'n', 't', 'i', 'c' 5 개의 알파벳은 반드시 포함해야 합니다. 따라서 K가 5미만인 경우에는 탐색할 필요 없이 '0'이 됩니다.
2. 만약 K가 26이라면, 알파벳의 총 개수만큼 뽑을 수 있으므로, 이 경우에도 탐색할 필요 없이 'N'이 됩니다.
3. K가 일반적인 경우라면, 우선 K에서 5를 뺍니다. 이는 반드시 포함해야 하는 알파벳 5개를 추가하고 남은 개수입니다.
4. 또한 visited 배열을 만들어서 우리가 이용할 수 있는 알파벳이 무엇 무엇인지 기록하는 용도로 사용합니다. 배열의 크기는 26이며, 알파벳마다 'a'를 빼는 연산을 수행해주면 됩니다. ('a' == 26)
5. 위 접근 방식에서 말씀드린 것처럼 문제를 푸는 방식은 remain이 0이 될 때까지 알파벳을 넣고, 0이 되는 순간에 우리가 만든 알파벳 집합(visited 배열)을 이용해 주어진 단어를 몇 개나 읽어낼 수 있는지 판단합니다.
6. 여기에서 주의해야할 점은 많은 완전 탐색 풀이가 그렇듯, 탐색의 순서는 다음과 같아야 합니다.
   1. 방문 상태를 확인하여 방문하지 않았다면 해당 알파벳을 방문한다.
   2. 방문한 알파벳을 방문 배열에 기록한다.
   3. 재귀 수행
   4. 방문 배열에 기록한 내역을 삭제한다. (방문 배열에 기록된 채로 다음 알파벳으로 넘어가면, 해당 알파벳을 다시는 방문할 수 없기 때문입니다. 예를 들어, 'a', 'b'가 기록되어 있는 상태에선, 'a', 'c'를 구할 수 없게 됩니다. 'a'가 이미 사용되었으니까요.)

이와 같은 내용에 유의하며 코드를 보여드리겠습니다. Go 언어로 작성되었습니다.

코드

package main

import (
    "bufio"
    "fmt"
    "os"
    "strings"
)

var (
    w       = bufio.NewWriter(os.Stdout)
    r       = bufio.NewReader(os.Stdin)
    result  int
    visited []bool
    words   []string
)

func main() {
    defer w.Flush()
    var N, K int
    fmt.Fscanf(r, "%d %d\n", &N, &K)
    words = make([]string, N)
    for i := range words {
        words[i] = getString()
    }
    if K < 5 {
        fmt.Fprintln(w, 0)
        return
    } else if K == 26 {
        fmt.Fprintln(w, N)
        return
    } else {
        visited = make([]bool, 26)
        visited['a'-'a'] = true
        visited['n'-'a'] = true
        visited['t'-'a'] = true
        visited['i'-'a'] = true
        visited['c'-'a'] = true
        solve(K-5, 'a')
        fmt.Fprintln(w, result)
    }
}

func solve(remain int, idx rune) {
    if remain == 0 {
        temp := 0
        for i := range words {
            flag := true
            for _, j := range words[i] {
                if !visited[j-'a'] {
                    flag = false
                    break
                }
            }
            if flag {
                temp++
            }
        }
        result = max(result, temp)
        return
    }

    for i := idx; i <= 'z'; i++ {
        if !visited[i-'a'] {
            visited[i-'a'] = true
            solve(remain-1, i)
            visited[i-'a'] = false
        }
    }
}

func getString() string {
    s, _ := r.ReadString('\n')
    s = strings.TrimSuffix(s, "\n")
    return s[4 : len(s)-4]
}

func max(a, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}