[파이썬] 백준 14238 : 출근기록 (골드2)

[파이썬] 백준 14238 : 출근기록 (골드2)

• https://www.acmicpc.net/problem/14238
  

---

문제

스타트링크에는 세명의 직원이 일을 하고 있다. 세 직원의 이름은 강호(A), 준규(B), 수빈(C) 이다.

이 회사의 직원은 특별한 룰을 가지고 있는데, 바로 하루에 한 명만 출근한다는 것이다. 3일간의 출근 기록이 "AAC"라는 것은 처음 이틀은 A가 출근했고, 셋째 날엔 C만 출근했다는 뜻이다.

A는 매일 매일 출근할 수 있다. B는 출근한 다음날은 반드시 쉬어야 한다. C는 출근한 다음날과 다다음날을 반드시 쉬어야 한다. 따라서, 모든 출근 기록이 올바른 것은 아니다. 예를 들어, B는 출근한 다음날 쉬어야 하기 때문에, "BB"는 절대로 나올 수 없는 출근 기록이다.

출근 기록 S가 주어졌을 때, S의 모든 순열 중에서 올바른 출근 기록인 것 아무거나 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 출근 기록 S가 주어진다. S의 길이는 50을 넘지 않는다.

출력

S의 모든 순열 중에서 올바른 출근 기록인 것을 하나만 출력한다. 만약, 올바른 출근 기록이 없는 경우에는 -1을 출력한다.

---

풀이

방향성 생각

• dfs + DP
• 상태에 영향을 주는 건 문자열의 맨 뒤 두자리
• 맨 끝자리에 B가 있으면 다음 B를 추가하는 branch는 탐색하지 못한다.
• 맨 끝 2자리에 C가 포함되어 있으면 다음 C를 추가하는 branch는 탐색하지 못한다.
  

전체코드

info = {'A':0,'B':0,'C':0}
for s in input():
    info[s] += 1

dp = set()

answer = None

def dfs(a,b,c,string):
    global answer

    if answer is not None: # 정답을 찾은 경우에는 탈출
        return

    if (a,b,c,string[-2:]) in dp: # 남은 abc 개수가 같고, 뒤 끝자리가 같으면 같은 상태이므로 중복 탐색 x
        return

    if (a,b,c) == (0,0,0): # 모두 출근 가능하면 정답 변경
        answer = string    
        return

    if a: # a에는 조건이 없다
        dfs(a-1,b,c,string+'A')
        dp.add((a,b,c,string[-2:]))
    if b: # b에는 맨 뒷자리가 B가 아닌 경우에 탐색
        if not string:
            dfs(a,b-1,c,'B')
            dp.add((a,b,c,string[-2:]))
        elif string and string[-1] != 'B':
            dfs(a,b-1,c,string+'B')
            dp.add((a,b,c,string[-2:]))
    if c: # c에는 뒤 2자리에 C가 없는 경우에 탐색
        if not string:
            dfs(a,b,c-1,'C')
            dp.add((a,b,c,string[-2:]))
        elif (len(string) == 1 and string[-1] != 'C') or (len(string) > 1 and 'C' not in set(string[-2:])):
            dfs(a,b,c-1,string+'C')
            dp.add((a,b,c,string[-2:]))

dfs(*(info.values()),'')

print(answer if answer != None else -1)

코멘트

• boj_12969와 비슷한 문제