[Python] BOJ 1012: 유기농 배추

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

요구사항

• 시간 제한 1초 
  • M x N = 250 
• 메모리 제한 512 MB  
  • 리스트 남발해도 끄떡없게 주심
• 최소의 배추흰지렁이 마리 수를 출력. 

설계

• BFS 를 사용해서 해결할 수 있다. 
  • 배추가 심어져 있는 땅이 얼마나 연결되어 있느냐? 를 생각하면 된다. 백준의 1926번을 풀어봤다면 쉽게 풀었을 듯 하다.
  • 문제를 볼 때, 지렁이 배추를 생각하면 되려 헷갈려 문제의 본질을 찾고, 내가 풀었던 문제들 중 가장 비슷한 문제를 떠올리면 쉽게 풀리는 거 같다. 
  • https://studyiwthme.tistory.com/185 <- 1926번 풀이 
• 배추 밭을 초기화하고 
• 배추가 심어져 있는 땅을 구하고
• 전체 필요한 지렁이를 초기화
• 방문 여부 처리 배열 초기화 
• BFS 탐색 함수를 생성하자 
  • 나만의 Tip 
  • 이 부분을 간략화 해서 외워두자. 안 외워도 하다보면 패턴이 외워진다. 
  • 문제마다 방문처리를 다르게 하는 문제들도 있으니, 어떻게 상하좌우로 이동하는 지 정도 외워두고 살을 붙이면 좋다. 
• 배추 밭 전체 탐색하여 필요한 최소 지렁이 수를 구해주자
  • 여기서 최소라고 해서 헷갈리는 데, 상하좌우로 연결된 하나의 그림의 개수를 count 한다고 생각하면 편하다.  

구현

from collections import deque

t = int(input())

for _ in range(t):
    # 가로, 세로, 배추가 심어져 있는 위치의 개수 
    m, n, k = map(int, input().split())
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    # 배추 밭 초기화
    area = [[0] * m for _ in range(n)]

    # 배추가 심어져 있는 땅 구하기  
    for _ in range(k):
        x, y = map(int, input().split())
        area[y][x] = 1  # 문제 정의에 따라 x는 가로, y는 세로 좌표

    # 전체 필요한 지렁이 초기화
    total_warm = 0

    # 방문 확인 배열
    visited = [[False] * m for _ in range(n)]

    # BFS 탐색 함수
    def bfs(start_x, start_y):
        queue = deque([(start_x, start_y)])
        visited[start_y][start_x] = True

        while queue:
            x, y = queue.popleft()

            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]

                if 0 <= nx < m and 0 <= ny < n and not visited[ny][nx] and area[ny][nx] == 1:
                    visited[ny][nx] = True
                    queue.append((nx, ny))

    # 배추 밭 전체 탐색
    for y in range(n):
        for x in range(m):
            if area[y][x] == 1 and not visited[y][x]:
                bfs(x, y)
                total_warm += 1
    
    print(total_warm)

실수 

프로그래머는 평균 10개의 실수를 한다고 한다. 실수를 기록해두어 앗, 내가 대충 이럴 때 이렇게 작성한 거 같은 데 정도의 기억을 가져가 보자, 오늘도 예전에 적은 게 어렴풋이 기억이 나, 실수를 잘 해결할 수 있었다. 

 

실수 1: 

while queue:
	for i in range(4):
    	x, y = queue.pop()

• 처음에 적었던 로직이다. 여기에는 2가지 실수가 담겨있다.
• 1 번째:
  • 예를 들어 현재 queue 리스트에 [ (0,0) ] 이 들어 있다 가정해보자. 
  • 그러면 0, 0 기준 상하좌우를 확인해야 된다. 그런데 위 소스코드에서는 queue 리스트를 4번이나 pop해주고 있다.
• 2 번째
  • 우리는 현재 deque 를 import 해서 사용하고 있다. FIFO 을 하려면 pop() 을 하는 게 아니라 popleft() 를 해야 된다. 

while queue:
	x, y = queue.popleft()
   for i in range(4):
    	. . .

실수 2: IndexError

area[x][y] = 1
IndexError: list index out of range 

• 토마토 문제에서 나를 3일이나 걸리게 해준 놈이다. https://studyiwthme.tistory.com/196
• 따라서 이번엔 문제를 다시 잘 읽고 행과 열을 신경 써주어 해결할 수 있었다. 
• 2가지 해결 방법이 있다.
  • 1 번째는 초기화할 때 사용한 m, n 위치를 바꿔준다.
  • 2 번째는 심어져 있는 배추의 위치를 초기화 할 때, x, y 좌표를 바꾼다. 
  • 나는 2 번 째 방법을 선택했다.