[내일배움캠프 21일차 TIL] 백준 1012 유기농 배추 with python

오늘은 백준의 1012번 유기농 배추 문제이다

문제는 다음과 같다

 

서로 인접해있는 배추가 몇 군데 퍼져있는가를 출력하는 문제이다

이 문제 역시 탐색 문제로 bfs또는 dfs를 이용해서 풀 수 있다

 

---

BFS를 이용한 풀이

-> 시간초과

처음엔 bfs를 이용해서 문제를 풀었다.

 

먼저 bfs 함수를 다음과 같이 정의해주고 (함수 이름 소문자로 했어야 했는데)

def BFS(field, que):
    while que: # 큐에 남은 좌표가 없을 때까지
        now = que.popleft() # 먼저 들어온 것 부터
        now_y, now_x = now[0], now[1] # y좌표, x좌표
        field[now_y][now_x] = 0 # 현재 좌표를 0으로 바꾸기
        for d in range(4): # 상하좌우 이동
            next_y, next_x = now_y + dy[d], now_x + dx[d]
            # 좌표가 범위 내에 있고, 좌표의 값이 1인 경우
            if (0 <= next_y < len(field)) and (0 <= next_x < len(field[0])) and (field[next_y][next_x]==1):
                que.append((next_y, next_x)) # 큐에 추가
    return field

 

테스트케이스를 입력 받고 배추밭의 가로, 세로, 배추의 개수를 입력 받았다

입력받은 배추밭의 가로 세로값으로 2차원 배열을 만들어주었고

입력받은 배추의 개수만큼 반복문을 돌려 배추의 위치를 배추밭에 입력해주었다

 

그리고 밭의 모든 위치를 방문하며 필요한 배추흰지렁이의 수를 구했다

물론 문제에 대한 답은 정상적으로 나왔지만 실제 제출에서는 시간초과가 떴다

 

그 이유에 대해 추측을 해보자면,

 

 

아마 이렇게 되면서 두 줄 이상 뭉쳐있는 경우에 탐색 비용이 더 들기 때문에 시간초과가 된 것이 아닌가 생각한다

 

 

---

 

 

깊이 우선 탐색을 이용한 풀이

반면 깊이 우선 탐색은 다음과 같다

중복됨 없이 쭉쭉이어진다

 

DFS 함수는 다음과 같이 정의하였다

def DFS(field, stack):
    while stack: # 스택에 좌표가 남아 있는 동안
        now = stack.pop() # 가장 마지막으로 추가된 것 부터
        now_y, now_x = now[0], now[1] # 좌표
        field[now_y][now_x] = 0 # 현재 위치를 0으로 교체
        for d in range(4): # 현재 위치에서 상하좌우로 이동
            next_y, next_x = now_y + dy[d], now_x + dx[d]
            # 좌표가 범위 내에 있고, 좌표의 값이 1일때
            if (0 <= next_y < len(field)) and (0 <= next_x < len(field[0])) and (field[next_y][next_x]==1):
                stack.append((next_y, next_x)) # 스택에 추가
    return field

 

그리고 위의 bfs와 마찬가지로

테스트케이스를 입력 받고 배추밭의 가로, 세로, 배추의 개수를 입력 받았다

입력받은 배추밭의 가로 세로값으로 2차원 배열을 만들어주었고

입력받은 배추의 개수만큼 반복문을 돌려 배추의 위치를 배추밭에 입력해주었다

그리고 밭의 모든 위치를 방문하며 필요한 배추흰지렁이의 수를 구했다

 

dfs는 시간초과 없이 통과하였다!

 

 

전체 코드는 여기서!

---

 

일반적으로 깊이우선탐색을 이용해 풀 수 있는 문제는 넓이 우선 탐색을 이용해서도 풀 수 있다

그런데 오늘 문제를 풀어보면서 둘의 차이가 크게 없다고 생각했는데 아니라는 것을 깨달았다...!

둘의 탐색 용도에 차이가 있고 조금 쓰임이 다를지도 모른다..!

사실 둘을 구분짓는 것이 크게 의미 없다고 생각했는데 오늘 문제를 풀면서 조금 더 깊이있게 이해 할 수 있게 된 것 같다!