[중등부] 2025 KOI 2차대회 대비 모의고사 (2회차)

지우는 광활한 필드에서 여행을 하려고 한다.

필드는 H행 W열의 격자 모양으로, 필드의 각 칸에는 땅이나 장애물(벽)이 있다.

지우가 필드에서 이동할 때 현재 위치에서 상, 하, 좌, 우 네 방향으로 이동할 수 있으며,
필드의 범위를 벗어난 방향 또는 벽이 있는 방향으로는 이동할 수 없다.

필드에는 P개의 마을이 있어서 각 마을에는 몬스터 치료소가 있다.

반대로, 마을이 없는 땅에는 강력한 야생 몬스터가 한 마리 살고 있어서 해당 땅을 지나가는 사람들을 공격한다.

지우는 안전한 여행을 위해 몬스터를 몇 마리 데리고 가려고 한다.

지우가 자기 몬스터들을 데리고 마을에 있는 몬스터 치료소에 방문하면 쓰러진 몬스터들을 모두 회복시킬 수 있다.

만약 지우가 마을이 없는 땅에 방문한다면 야생 몬스터가 지우가 데리고 있는 살아있는 몬스터를 한 마리 공격한다.

공격받은 몬스터는 쓰러지며 몬스터 치료소에 방문하여 치료하기 전까지는 되살아나지 않는다.

만약 지우의 모든 몬스터가 쓰러진 상태에서 야생 몬스터를 만난다면 야생 몬스터가 지우를 공격하게 되어 지우가 쓰러진다.

같은 지역에 여러 번 방문한다면 야생 몬스터는 해당 지역에 방문할 때마다 공격을 실시한다.

지우는 자신이 공격받지 않도록 몬스터를 적당히 데리고 한 마을에서 다른 마을로 여행하려고 한다.

하지만 몬스터를 너무 많이 데리고 간다면 짐가방이 무거워지므로 몬스터는 가능한 한 최소한만 데리고 가려고 한다.

지우의 여행계획 Q개에 대하여 해당 여행에 필요한 최소 몬스터 수를 구하는 프로그램을 작성하여라.