백준 1012 유기농 배추 (Python)

문제링크 : https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

dfs/bfs + 상하좌우로 움직이는 문제

 

여기 예시에서는 1을 잇는 덩어리가 5개이므로 답은 5

 

일반적인 dfs, bfs문제와 다르게 상하좌우로 움직이는 것을 생각해야 하는데, 이는 꽤 코딩테스트에도 나올 가능성이 있는 문제라고 생각한다.

 

생각해내야할 중요한 부분은

1. 상하좌우 이동 변수 만들기

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

2. for i in range(4)를 돌면서 dfs로 체크

for i in range(4): 
    posx = x + dx[i]
    posy = y + dy[i]

    if (0 <= posx < n) and (0 <= posy < m):
        if vegetable_list[posx][posy] == 1:
            vegetable_list[posx][posy] = 0
            dfs(posx, posy, m, n, vegetable_list)