[BOJ][🟡4][백준#16432] 떡장수와 호랑이

문제 출처

BAEKJOON Online Judge #16432

문제

떡장수 동희는 매일 새벽에 갓 만든 떡을 들고 산을 넘어 장터로 가서 떡을 팝니다. 동희가 만드는 떡의 종류는 1번부터 9번까지 있습니다. 산에는 동희가 나타나기를 기다렸다가 동희를 협박하여 떡을 하나 가져가는 호랑이가 살고 있습니다. 이 호랑이는 입맛이 까다로워 전날에 먹었던 떡과 같은 종류의 떡이면 먹지 않습니다. 만약 줄 수 있는 떡이 없다면 동희는 호랑이에게 잡아먹히고 맙니다. 동희는 N일 동안 떡을 팔러 매일 장터에 나가야 합니다. 동희가 만드는 떡들의 종류는 재료 공급 사정에 따라 종류가 매일 달라집니다.  동희가 N일 동안 호랑이에게 잡아먹히지 않도록 호랑이에게 줄 떡들을 골라주세요.

입력

첫 번째 줄에 동희가 떡을 팔아야 할 날의 수 N이 (1 ≤ N ≤ 1,000) 이 주어집니다. i+1 (1 ≤ i ≤ N) 번째 줄에는 mi, ai,1, ai,2, …, ai,mi (1 ≤ mi ≤ 9, 1 ≤ ai,1 < ai,2 < … < ai,mi ≤ 9) 가 주어지는데 mi는 동희가 i번째 날 들고 가는 떡들의 개수이고 ai,j는 동희가 가져가는 떡의 종류입니다.

출력

동희가 N일동안 호랑이에게 떡을 줄 방법이 있다면 i (1 ≤ i ≤ N) 번째 줄에 동희가 호랑이에게 주어야 할 떡을 출력합니다. 이 떡은 동희가 i번째 날에 만든 떡이어야 합니다. 만약 동희가 떡을 줄 방법이 없다면 첫 번째 줄에 ‘-1’ 하나만 출력하고 더 이상 아무것도 출력하지 않아야 합니다.  방법이 여러 가지인 경우 그 중 하나만 출력합니다.

예제

예제 1

입력

3
3 1 2 3
2 1 2
2 2 3```

<br>

출력

2 1 3```

예제 2

입력

3
3 7 8 9
1 1
1 1

출력

-1

My Sol

def check(i):
    global dds
    if len(dds[i]) == 1:
        d = dds[i].pop()
        dds[i].add(d)
        prev = i-1
        next = i+1
        if prev > -1 and (d in dds[prev]):
            dds[prev].remove(d)
            check(prev)
        if next < N  and (d in dds[next]):
            dds[next].remove(d)
            check(next)

N = int(input())
dds = []
for i in range(N):
    n, *arr = map(int, input().split())
    dds.append(set(arr))

for i in range(N):
    check(i)

for dd in dds:
    if not dd:
        print(-1)
        quit()

prev = dds[0].pop()
print(prev)
for i in range(1, N):
    if prev in dds[i]:
        dds[i].remove(prev)
    prev = dds[i].pop()
    print(prev)

set의 hash와 DFS를 이용하여 문제를 풀었다.

1. 이전이 아니라, 전날 내놓은 떡과 같은 떡이 아니기만 하면 된다.
2. 만약 떡의 개수가 하나인 경우 다른 떡을 내놓을 수 없다.
3. 전체 떡의 리스트에서 하나의 떡을 가진 날을 포착한다.
4. 전날과 다음날 같은 떡을 내놓으면 안 되므로 제거한다.
5. 만약 같은 떡을 가지고 있는 경우 제거하면 제거로 인해 떡이 하나가 되었는지 체크한다.
6. 즉, 제거 후 check하는 함수를 한 번 더 DFS 재귀하여 체크를 한다.
7. 모든 체크를 마지면, 불가능한 경우는 특정 날의 set은 set()으로 비어있다.
8. 이런 경우가 아니라면 그냥 매일의 떡을 pop하여 하나만 뽑아 출력한다.
9. 이때 이전 날과 우연히 같으면 안되므로 prev를 따로 설정해두어 겹치지 않도록 다음날의 set에서 제거하고 하나를 뽑는다.

결과

맞았습니다!!