MungGu Story

백준 16956, 늑대와 양 문제 개요, 애드혹(ad-hoc)이란? 오늘은 백준 16956, 늑대왕 양 문제를 풀어보겠습니다. 해당 문제는 애드혹 문제로, 애드혹이란 특정 접근방법 없이 창의적 아이디어를 활용해서 풀 수 있는 문제라고 합니다. 실버3 티어의 문제로, 늑대에게 양이 잡아먹히지 않도록 울타리를 놓을 수 있다면 1과 그래프 상태를, 늑대에게 잡하먹힐 수밖에 없다면 0을 출력하는 문제입니다. 해당 문제의 중요한 점은 울타리를 놓는데 제한이 없다는 것입니다. 몇개의 울타릴 놓던간에, 양이 먹히지만 않으면 됩니다. 그렇게 제가 생각한 것은 "모든 양과 늑대가 처음에 붙어있지만 않는다면 무조건 양이 울타리를 놓아 살 수 있다" 입니다. 그리고, "양이 살기 위해 최대한 자신의 주변의 빈공간에 울타리를..