[Baekjoon] 1012_유기농 배추

Silver II

문제(출처: https://www.acmicpc.net/problem/1012)

---

<유기농 배추>

문제 

 

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추 흰 지렁이를 구입하기로 결심한다. 이 지렁이는 배추 근처에 서식하며 해충을 잡아먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추 흰 지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.
한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추 흰 지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추 흰 지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

 

입력

 

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로 길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그다음 K 줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

 

출력 

 

각 테스트 케이스에 대해 필요한 최소의 배추 흰 지렁이 마리 수를 출력한다.

 

 

문제 풀이

- my solution

import sys
from collections import deque

def bfs(graph,start,visited,m,n): #너비 우선 탐색
    dx=[-1,0,0,1] #상좌우하
    dy=[0,-1,1,0]
    temp=deque([start])

    while temp:
        k=temp.popleft()
        visited.append(k) # 방문하면
        for i in range(4):
            x=k[0]+dx[i]
            y=k[1]+dy[i]
            if x>=0 and x<m and y>=0 and y<n: # 범위 확인
                if [x,y] in graph and [x,y] not in visited: # 배추가 있고 아직 방문하지 않았으면
                    graph.remove([x,y]) # 방문할 것이므로 main에서 반복문 돌 필요 없음
                    temp.append([x,y])


if __name__=='__main__':
    t=int(input()) # 테스트 케이스

    for i in range(t):
        m,n,k=map(int,sys.stdin.readline().split())
        visited=[]
        arr=[]
        for i in range(k): # 배추 위치
            x=list(map(int, sys.stdin.readline().split()))
            arr.append(x)

        cnt=0
        for i in arr:
            if i not in visited: # 아직 방문하지 않았으면
                cnt+=1
                bfs(arr,i,visited,m,n)
        print(cnt)

 

 

bfs에 대해서 찾아보다가 deque의 popleft를 사용한다는 글을 보고 여기서 활용해보았다. 뭐가 맞는지 정말 모르겠다. 조만간 책을 찾아서 확인해봐야겠다!

 

• bfs(list, 시작 위치 , 방문 여부 list, 배추 밭의 가로길이, 배추 밭의 세로 길이)
  - 연결된 부분을 찾아야 하기 때문에 상좌우하를 보기 위해 dx, dy 선언
  - temp deque에 시작 위치 x, y 좌표 넣어서 선언
  - temp list가 빌 때까지 반복: temp에서 맨 앞 값을 뽑아와 아직 방문한 집이 아니라면 visited에 표시, 상좌우하 확인하여 배추 밭의 가로, 세로 범위에 속하고, 아직 방문하지 않았다면 배추 위치 list에서 제거와 temp list에 x, y 좌표 추가
  
  
• main
  - 테스트 케이스 수 입력
  - 배추 밭의 가로, 세로 길이와 배추 위치 개수 입력
  - 배추 위치 입력
  - 배추 위치 순회하며 아직 방문하지 않았으면 bfs 호출 -> 호출할 때마다 배추 흰 지렁이 필요 +1
  
  

처음에 문제를 잘 푼 것 같았는데 시간 초과가 발생하여 잠시 접었었던 문제이다.

오늘 다시 코드를 보며 시간 초과가 난 이유를 살펴보다가 딱 한 줄을 추가하니 통과할 수 있었다.

 

시간 초과 이유: 

한 배추 위치에서 상하좌우를 살펴봤을 때 배추가 존재한다면 그 배추로 이동하여 계속해서 탐색할 것이다.

main문에서 이미 bfs로 탐색했던 부분도 또 탐색하므로 시간 초과가 발생하는 것이다.

그러므로 bfs 함수 안에서 상하좌우를 살펴봐 그 배추로 이동하면 main문에서 탐색할 필요가 없으므로 list에서 제거해주어야 시간 초과가 발생하지 않는다.

 

내가 생각한 시간 초과 이유는 위와 같다. 코드 한 줄을 추가하니 바로 통과할 수 있었다. 

 

---

생각🤔

 

문제가 풀리지 않을 때는 잠시 접었다가 다시 보는 것이 더 좋을지도 ㅎㅎ

 

---