난이도 : Silver1
Link : https://www.acmicpc.net/problem/27737
Tag : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
풀이일자 : 2024년 9월 11일

📌 문제 탐색하기

정사각형으로 이뤄진 나무판에서 M개의 버섯 포자를 가지고 농사가 가능한지 불가능한지, 사용 가능한 버섯 포자의 개수는 몇개인지 구하는 문제이다.
N : 나무판의 크기
M : 포자의 개수
K : 포자가 자라게 하는 버섯의 개수
1 : 버섯이 자랄 수 없는 칸
0 : 버섯이 자랄 수 있는 칸

가능한 시간복잡도

완전 탐색의 문제로 N의 크기별로 문제의 시간복잡도는 달라지게 된다.
N의 크기는 100까지 이므로 최대 반복할 수 있는 시간복잡도는 100 x 100 = 10000이므로 완전탐색인 BFS로 접근이 가능하다.

📌 문제 접근 방법

1. 전체 나무판에서 for문을 이용하여 육지를 찾는다.
2. 나무판에서 0을 찾았다면 BFS를 이용하여 주변의 0을 탐색한다.
3. 탐색한 곳의 개수를 찾아 반환한다. mursh
4. 한 그룹의 0의 개수를 다 셌다면 needed_mursh에 (mursh + k -1) // k 로 필요한 포자의 개수를 구한다.
5. 필요한 포자의 개수가 m 보다 작다면 농사가 가능하고, m보다 크다면 농사가 불가능하다고 판단하면 될것이다.

📌 코드 설계하기

1. n,m,k 를 입력받고, grid에 나무판을 입력받는다.

2. answer변수을 0으로 초기화 하고 needed_mursh 변수를 만든다 (필요한 포자 개수)

3. 4방향으로 이동할 수 있는 방향을 설정한다.

   #4방향
   dx = [1,-1 ,0 ,0]
   dy = [0, 0, 1, -1]

4. BFS 함수를 작성한다.

   • queue에 처음 좌표를 넣어준다.
   • 처음 좌표의 0을 1로 바꿔 재탐색을 방지한다.
   • queue에 원소가 존재할때 동안 x,y를 업데이트 해준다.
   • 4방향으로 이동했을때 이동할 수 있는 지 파악하고 0일 경우 1로 변경한다.
   • 0을 찾을때마다 mursh 변수에 1씩 추가한다.

5. 나무판을 반복하여 0인 나무판을 찾아 BFS 함수를 호출한다.

6. mursh에 BFS로 탐색하여 찾은 0의 개수를 넣어주고 needed_mursh를 구해 answer를 업데이트 한다.

7. answer의 값이 m보다 작거나 같고, needed_mursh > 0 사용한 포자가 1개 이상이라면 POSSIBLE을 출력하고 answer - m을 출력한다.

8. 그렇지 않다면 IMPOSSIBLE을 출력한다.

📌 시도 회차 수정 사항

틀렸습니다. (최소 1개 이상 포자를 사용할때를 제외 시킴)

from collections import deque

n,m,k = map(int,input().split())
grid = [list(map(int,input().split())) for _ in range(n)]
answer = 0
def BFS(x, y):
    queue = deque([(x,y)])
    grid[x][y] = 1
    mursh = 1
    dx = [1,-1 ,0 ,0]
    dy = [0, 0, 1, -1]
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0<=nx<n and 0<=ny<n and grid[nx][ny]==0:
                queue.append((nx,ny))
                grid[nx][ny] = 1
                mursh += 1
    return mursh

for i in range(n):
    for j in range(n):
        if grid[i][j]==0:
            mursh = BFS(i,j)
            needed_mursh = (mursh+ k -1) // k
            answer += needed_mursh

if answer <= m:
    print("POSSIBLE")
    print(m-answer)
else:
    print("IMPOSSIBLE")

📌 정답 코드

from collections import deque

n,m,k = map(int,input().split())
grid = [list(map(int,input().split())) for _ in range(n)]
answer = 0
needed_mursh = 0
def BFS(x, y):
    queue = deque([(x,y)])
    grid[x][y] = 1
    mursh = 1
    dx = [1,-1 ,0 ,0]
    dy = [0, 0, 1, -1]
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0<=nx<n and 0<=ny<n and grid[nx][ny]==0:
                queue.append((nx,ny))
                grid[nx][ny] = 1
                mursh += 1
    return mursh

for i in range(n):
    for j in range(n):
        if grid[i][j]==0:
            mursh = BFS(i,j)
            needed_mursh = (mursh+ k -1) // k
            answer += needed_mursh

if answer <= m and needed_mursh > 0:
    print("POSSIBLE")
    print(m-answer)
else:
    print("IMPOSSIBLE")