[BOJ] 1012번 - 유기농 배추

문제

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

1012번: 유기농 배추

🚦 문제 유형

• 그래프 탐색
• bfs, dfs

 

✅ 문제 설명

• 유기농 배추를 재배하려면 해충 방지에 효과적인 배추흰지렁이를 구입해야 합니다.
• 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면, 인접한 다른 배추도 해충으로부터 보호받습니다.
• 인접한 배추는 '상하좌우' 입니다.
• 군데군데 심어져있는 배추를 보호하기 위해서 최소 몇 마리의 지렁이가 필요한지 구해야 합니다.
  
  
• 입력의 첫 줄: 테스트 케이스 개수
• 입력의 두번째 줄: 배추밭의 가로길이, 세로길이, 배추 개수
• 다음 줄: 배추가 심어져있는 위치 X(배추밭의 가로길이 기준), Y(배추밭의 세로길이 기준)
• 여기서 주의깊게 살펴야 하는 부분: 배추밭의 가로, 세로길이와 배추의 위치는 우리가 알고 있는 (행, 열)의 개념과 반대되고 있다. 따라서 원래 (행, 열) 표기가 편하다면, 그래프를 초기화 할 때 주의해야 합니다.

 

✏️ Solution

• dfs, bfs 모두 풀 수 있습니다.

먼저 배추 밭 그래프를 생성한다. (가로, 세로를 유념하여 가로가 열, 세로가 행이 되도록 그래프를 생성했다.)

graph = [[0]*M for _ in range(N)]	# 올바른 코드

graph = [[0]*M]* N	# 오류

처음에는 2번째로 작성했다가 정답이 나오지 않아 몇 번 찍어보니 오류가 있었다.

(1,0)을 업데이트 하면 (2, 0), (3, 0) ... 이 전부 동일한 값으로 업데이트 되었다. 아마 저렇게 작성하면 복제의 개념으로 생성되는 것 같다.

 

그리고 배추가 심어져있는 곳을 1로 표시한다. 이 때 X, Y를 입력받을 때 (행, 열)로 받아야 하기 때문에 둘의 순서를 바꿔주면 된다.

• 예시에서 가로 -> 그래프의 열
• 예시에서 세로 -> 그래프의 행

 

그래프를 순차적으로 확인하면서 배추가 인접해서 심어져있는지 확인하고 그에 따른 배추흰지렁이 개수를 카운트하면 끝이다.

이 과정을 DFS, BFS로 풀 수 있다.

배추가 심어져있으면(=그래프의 원소가 1이라면), 그 자리에서 너비 또는 깊이 탐색을 한다.

탐색이 끝나면 -> 인접한 배추들을 다 돌았으므로 배추흰지렁이 개수를 하나 up 한다.

 # 그래프를 확인하면서 배추가 심어져있는지 확인 -> 인접한 배추가 있는지 확인
    count = 0   # 배추흰지렁이 개수
    for n in range(N):  # 행=세로길이
        for m in range(M):  #열=가로길이
            if graph[n][m] == 1:    # 배추가 있는 칸을 발견하면,
                bfs(graph, n, m)    # 그 칸에서 상하좌우 탐색(bfs수행)해서 그 구역의 1은 모두 0으로 바뀌므로, 배추 흰지렁이 개수는 1개만 필요함.
                count += 1  #1인 칸을 발견할 때 마다 카운트한다.
    print(count)

 

이제 남은 구현은 dfs와 bfs 함수이다.

사실 이 부분이 제일 어렵다. 익숙해져야 헷갈리지 않고 작성할 수 있을 것 같다.

1. BFS 풀이

기본적인 bfs 함수를 작성하는 큰 틀은 다음과 같다.

문제마다 활용하는 방식이 다르지만 큰 틀은 벗어나지 않는 것 같다.

def bfs(탐색할 그래프, 현재 위치하고 있는 인덱스(ex. 행, 열)):
	# bfs는 queue(큐)에 방문할 노드를 삽입하고,
    queue = deque()
    queue.append((x, y))
    
    # queue가 모두 비워질 때 까지 하나씩 꺼낸다.
    while queue:
    	x, y = queue.popleft()
        
    # 노드를 하나 꺼낸 뒤 해당 노드는 '방문처리'를 꼭 해주고(다시 방문하지 않도록)

    # 꺼내진 노드는 '문제에서 요구하는 어떤 처리'를 거친다.
    
    # queue가 모두 비워지면 bfs 함수는 종료된다.

이 문제에서 요구하는 어떤 처리는 '상하좌우에 인접한 배추가 있는지 탐색' 하는 것이다.

보통 그래프에서 상하좌우 탐색은 dx, dy를 많이 사용하니 기억하면 좋다.

dx = [-1,1,0,0] # 상하좌우 x 좌표
dy = [0,0,-1,1] # 상하좌우 y 좌표

 

현재 방문한 노드의 '상하좌우'를 탐색할 때,

• 상하좌우 결과가 그래프의 범위를 벗어나지 않는지
• 상하좌우 결과, 배추가 심어져있는지

이 2개는 반드시 확인해야 한다.

배추가 심어져있다면, 인접한 공간에 배추가 있는 것이니 다시 그 배추의 상하좌우를 살펴야 하고 

따라서 해당 노드를 큐에 삽입해줌으로써 다음에 방문할 수 있도록 한다.

dx = [-1,1,0,0] # 상하좌우 x 좌표
dy = [0,0,-1,1] # 상하좌우 y 좌표

# bfs 함수
def bfs(graph, n, m):   # 그래프 정보와 현재 노드의 위치 (n, m)을 인자로 받는다.
    queue = deque() # 하나씩 방문하기 위해 큐를 생성하고
    queue.append((n, m))    # 방문한 노드는 큐에 삽입한다.
    graph[n][m] = 0 # 방문한 노드를 0으로 업데이트 한다.
    
    while queue:   # 큐가 다 빌 때까지 = 방문할 노드가 하나도 없을 때 까지
        x, y = queue.popleft()  # 방문할 원소를 하나 꺼낸다. 전에 (n, m)이 큐에 append 되었다.
        
        for i in range(4):  # 그 원소의 상하좌우를 살펴볼 예정,
            nx = x + dx[i]  
            ny = y + dy[i]
            
            if nx<0 or nx>=N or ny<0 or ny>=M:  # 상하좌우 중 범위를 벗어난다면, 무시하고 진행
                continue
            
            if graph[nx][ny] == 1:  # 상하좌우 이동 결과, 배추가 있다면,
                graph[nx][ny] = 0   # 방문했다고 표시한다.
                queue.append((nx, ny))  # 다시 이 배추를 중심으로 상하좌우를 방문해야 하므로 이 노드를 큐에 저장한다.
    return

 

전체 코드는 다음과 같다.

# bfs 풀이

from collections import deque
import sys

T = int(input())    # 테스트 케이스의 개수

dx = [-1,1,0,0] # 상하좌우 x 좌표
dy = [0,0,-1,1] # 상하좌우 y 좌표

# bfs 함수
def bfs(graph, n, m):   # 그래프 정보와 현재 노드의 위치 (n, m)을 인자로 받는다.
    queue = deque() # 하나씩 방문하기 위해 큐를 생성하고
    queue.append((n, m))    # 방문한 노드는 큐에 삽입한다.
    graph[n][m] = 0 # 방문한 노드를 0으로 업데이트 한다.
    
    while queue:   # 큐가 다 빌 때까지 = 방문할 노드가 하나도 없을 때 까지
        x, y = queue.popleft()  # 방문할 원소를 하나 꺼낸다. 전에 (n, m)이 큐에 append 되었다.
        
        for i in range(4):  # 그 원소의 상하좌우를 살펴볼 예정,
            nx = x + dx[i]  
            ny = y + dy[i]
            
            if nx<0 or nx>=N or ny<0 or ny>=M:  # 상하좌우 중 범위를 벗어난다면, 무시하고 진행
                continue
            
            if graph[nx][ny] == 1:  # 상하좌우 이동 결과, 배추가 있다면,
                graph[nx][ny] = 0   # 방문했다고 표시한다.
                queue.append((nx, ny))  # 다시 이 배추를 중심으로 상하좌우를 방문해야 하므로 이 노드를 큐에 저장한다.
    return
    

for t in range(T):
    M, N, K = map(int, input().split()) # 가로(열), 세로(행), 배추 개수
    # graph = [[0]* M] * N   # 행(N;세로 길이), 열(M;가로 길이)로 그래프를 만든다.    -> 잘못된 코드; graph[0][1]를 업데이트 할 때 graph[1][1], graph[2][1]등 모두 업데이트 되는 문제가 발생한다.(복제된 버전일까?)
    
    graph = [[0]*M for _ in range(N)]
    
    for k in range(K):
        x, y = map(int, input().split())  # 배추위치를받고,(x는 가로(열), y는 세로(행))
        graph[y][x] = 1 # 배추가 있다고 표시한다.
    
    # 그래프를 확인하면서 배추가 심어져있는지 확인 -> 인접한 배추가 있는지 확인
    count = 0   # 배추흰지렁이 개수
    for n in range(N):  # 행=세로길이
        for m in range(M):  #열=가로길이
            if graph[n][m] == 1:    # 배추가 있는 칸을 발견하면,
                bfs(graph, n, m)    # 그 칸에서 상하좌우 탐색(bfs수행)해서 그 구역의 1은 모두 0으로 바뀌므로, 배추 흰지렁이 개수는 1개만 필요함.
                count += 1  #1인 칸을 발견할 때 마다 카운트한다.
    print(count)

 

2. DFS 풀이

- 곧 작성

 

⚙️ Review

오랜만에 그래프 문제를 풀었는데 dfs, bfs 개념이 많이 약해져있다. 개념을 잊지 않도록 다시 공부가 필요하다.

문제에서 주어진 (가로, 세로)가 파이썬의 (행, 열)과 반대된다는 점이 너무 헷갈렸다. 다음에 이런 문제를 만난다면 더 섬세하게 고려해서 풀어야겠다.

아무리 풀어도 해결되지 않았는데 어이없는 실수가 있었다. 상하좌우 이동결과 그래프의 범위안에 있는지 확인하는 코드에서 변수를 잘못넣었다. 이런 자잘한 실수는 역시 주석을 섬세하게 달아야 해결되는 것 같다.

류호석님의 코테 영상에서, 주석을 꼼꼼히 달아야 코드 작성하기가 더 편해진다고 그러셨다. 처음엔 이해 못했는데 요즘 코테 풀면서 확실히 느낀다. 나의 실수를 더 빨리 찾을 수 있다. 

다음 코드에서는 주석을 더 자세하게 작성하려고 한다.