[Algorithm][BOJ] 1012번 - 유기농 배추 (Python)

👇문제 링크👇
boj 1012 유기농 배추

💡 문제 파악하기

• 배추흰지렁이는 인접한 다른 배추로 이동이 가능하다. (인접 = 상 / 하 / 좌 / 우)
• 배추가 몇 군데에 퍼져있는지 조사하기

💡 문제 풀기

• DFS 활용 => 깊이 우선 탐색
• [상 / 하 / 좌 / 우]에 대해 좌표로 정리하여 list형태로 저장
• python Collections module에서 deque 활용
  - deque : "스택과 큐의 기능을 한번에!"
  

💻 Code

from collections import deque

# 방향과 관련된 좌표 list 형태로 저장 [우, 좌, 상, 하]
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

# 탐색을 시작할 좌표값과, 전제 땅 모양을 인자로 받는다
def dfs(start, ground):
    queue = deque()
    queue.append(start)
    while queue:
        y, x = queue.popleft()
        # 확인한 구역은 0으로 바꿔주기
        ground[y][x] = 0
		
        # 상/하/좌/우 로 이동하면서 배추가 심어진 구역이 있는지 탐색한다.
        for move in dirs:
            move_y, move_x = y + move[0], x + move[1]
			
            # 배추를 심은 곳을 발견한다면, queue에 좌표값을 넣고, 그 지역을 중심으로 다시 탐색해본다
            if 0 <= move_y < N and 0 <= move_x < M and ground[move_y][move_x] == 1:
                queue.append((move_y, move_x))
                ground[move_y][move_x] = 0

# test case의 개수를 input 값으로 받기
test_num = int(input())


for i in range(test_num):
    M, N, K = map(int, input().split())
    # 땅을 나타내는 행렬을 0으로 초기화 시켜준다
    ground = [[0] * M for _ in range(N)]
    cnt = 0
    
    # 배추가 심어져 있는 구간을 입력받고, 해당하는 ground의 좌표를 1로 바꿔준다
    for j in range(K):
        x, y = map(int, input().split())
        ground[y][x] = 1
	
    # ground의 모든 부분에 대하여 배추가 심어져 있는 구간이라면, 
    # dfs를 실행하여 인접한 배추가 있는지 확인한다.
    for w in range(M):
        for h in range(N):
            if ground[h][w] == 1:
                cnt += dfs((y, x), ground)

    print(cnt)

💡 추가

• List Comprehension (리스트 내포)

  new_list = [expression for member in iterable (if conditional)]

  • 내 코드에서는 ground = [[0] * M for _ in range(N)] 이렇게 활용했다.

• 2차원 배열에서의 x,y좌표 표기
  • 수학에서 쓰는 (x,y)와 다르게 python 이차원 리스트에 접근 할 때에는 [y][x] 순서로 해 주어야 한다.
  • S[세로인덱스][가로인덱스]

앞으로 열심히 블로그 글 올리는게 저의 목표입니당👍