백준 1012번 유기농배추

문제 링크

https://www.acmicpc.net/problem/1012

풀이 전 계획과 생각

이 문제는 살펴보면 2667번 단지번호붙이기와 내용이 거의 같은 문제다. 2667번에서는 서로 상하좌우로 연결되어 있는 집이 같은 단지로 분류되고, 여기에서는 서로 상하좌우로 연결되어 있는 배추는 지렁이 한 마리 아래(...)에 있는 것으로 간주한다.
2667번에서는 단지가 몇 개인지 센 뒤에 각 단지에 있는 가구 수를 오름차순으로 정렬해 출력하지만, 여기에서는 지렁이 한 마리 아래에 배추 몇 개가 있는지는 출력하지 않고 지렁이가 몇 마리 필요한지만 출력한다.

출제자분은 거의 같은 문제라서 너무 쉬울까 봐(???) 이 문제의 입력 절차를 엄청나게 까다롭게 만들어 놓으신 것 같다. 그냥 가로 세로 길이와 배추 개수와 배추가 있는 좌표만 입력하고 끝나는 게 아니라, 그런 테스트 케이스의 묶음이 몇 개인지(!) 또 입력을 해서 배추 맵을 여러 개를 처리해야 하게 만들고 있다.

풀이 (코드 블록 첨부)

import collections
import sys
T=int(input())
tables=[]
for i in range(T):
    M,N,K=map(int,sys.stdin.readline().split())
    loc=[[0]*(N) for x in range(M)]
    for j in range(K):
        x,y=map(int,sys.stdin.readline().split())
        loc[x][y]=1
    tables.append(loc)
#print(tables)
def bfs(arr):
    #current_unit_no=1
    current_cnt=0
    visited=[[0]*(len(arr[0])) for x in range(len(arr))]
    
    for i in range(len(arr)):
        for j in range(len(arr[0])):
            if arr[i][j]==0:
                continue
            if visited[i][j]==1:
                continue
            to_visit=collections.deque([[i,j]])
            current_cnt+=1
            while to_visit:
                current_loc=to_visit.popleft()
                visited[current_loc[0]][current_loc[1]]=1
                to_compare = [[current_loc[0]-1,current_loc[1]],\
                              [current_loc[0]+1,current_loc[1]],
                              [current_loc[0],current_loc[1]-1],
                              [current_loc[0],current_loc[1]+1]]
                for element in to_compare:
                    if element[0]>=0 and element[0]<len(arr) and \
                       element[1]>=0 and element[1]<len(arr[0]) and \
                       arr[element[0]][element[1]]==1 and \
                       visited[element[0]][element[1]]==0:
                        to_visit.append(element)
    print(current_cnt)
                       
            
for table in tables:
    bfs(table)

풀이하면서 막혔던 점과 고민

앞서 말했지만 앞의 2667 단지번호붙이기 문제와 거의 동일하다. 아니, 솔직히 말하자면 앞 문제가 너무 이해가 안 가고 코드가 다 꼬였다가 이걸 먼저 풀어본 구조를 바탕으로 다시 진행해볼 수 있었다.

풀이 후 알게된 개념과 소감

BFS를 열심히 공부하였다.
그러나...
이것도 백준 온라인 저지 채점 프로그램에서는 시간초과가 떴다 ㅠㅠ
어떻게 더 줄일 수 있는지는 다음에 다시 공부해봐야겠고... 여기까지 풀어보는 데도 너무 시간이 많이 걸려서 이번 주는 여기까지만 하려고 한다.