[파이썬/백준] 1012번 : 유기농배추

 

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

 

 

문제 설명

 

 

 

 

 

 

배추흰지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호

한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것

-> 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다.

 

예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

 

 

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다.

첫째 줄 : 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)

그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

 

배추가 심어진 위치의 개수 -> cnt     (반복문의 횟수로 사용해야 한다.)

 

 

 

문제 풀이

 

배추의 위치를 반복문으로 찾으면서 상하좌우에 없으면 지렁이 수를 증가하는 형태로 작성하면 될 것 같다.

 

dfs / bfs를 활용하여 풀면될 듯 하다.

 

그래프 탐색 알고리즘

그래프 구조에서 특정 노드나 경로를 찾기 위해 사용되는 알고리즘

대표적인 그래프 탐색 알고리즘으로는 깊이 우선 탐색(DFS, Depth-First Search)과 너비 우선 탐색(BFS, Breadth-First Search)이 있다.

 

 

깊이 우선 탐색(DFS)

• 그래프의 한 노드에서 시작하여 가능한 한 깊이 내려가면서 탐색을 진행하는 알고리즘
•  스택 자료구조를 사용하여 구현
• 재귀적으로도 구현
• 가능한 한 깊이 내려가면서 탐색을 진행하기 때문에 특정 경로를 찾거나, 그래프의 모든 노드를 방문하는 데 유용

 

 

너비 우선 탐색(BFS)

• 그래프의 한 노드에서 시작하여 인접한 노드를 먼저 탐색한 후, 그 다음 인접한 노드를 탐색하는 방식으로 진행하는 알고리즘
• 큐 자료구조를 사용하여 구현
• 접한 노드를 먼저 탐색하기 때문에 BFS는 최단 경로를 찾는 데 유용

 

아래와 같은 순서로 코드를 작성하면 될 듯 하다.

 

1. 배추의 위치를 입력받아 표시

2. 배추밭에서 이동하면서 배추를 발견하면, 지렁이 +1 하고 dfs 호출

3. dfs에서 상하좌우 돌면서 배추인지 확인하고, 배추이면 dfs 재귀호출

4. 2번~3번 과정 반복 후, 최종 지렁이 수 출력

 

 

import sys
sys.setrecursionlimit(10000)     # 재귀한도 설정

def dfs(x, y):
    dx = [0, 0, -1, 1]           # 상하좌우 이동을 위한 x축 변화 값 배열
    dy = [1, -1, 0, 0]           # 상하좌우 이동을 위한 y축 변화 값 배열
    
    for i in range(4):           # 상하좌우 네 방향을 반복
        nx = x + dx[i]           # 새로운 x 좌표는 현재 좌표에 이동 값을 더한 값
        ny = y + dy[i]           # 새로운 y 좌표는 현재 좌표에 이동 값을 더한 값
        if (0 <= nx < m) and (0 <= ny < n):       # 새로운 좌표가 배열의 범위를 벗어나지 않게 함
            if field[ny][nx] == 1:				  # 만약 배추가 위치해 있다면
                field[ny][nx] = 0				  # 방문했으므로 0으로 바꿈
                dfs(nx, ny)                       # 새 좌표에서 다시 DFS를 호출하여 배추 탐색
                
for _ in range(int(sys.stdin.readline())):                # 테스트 케이스의 수만큼 반복
    m, n, k = map(int, sys.stdin.readline().split())      # m:가로길이, n:세로 길이, k:배추개수
    field = [[0 for _ in range(m)] for _ in range(n)]     # field라는 m x n 배열을 0으로 초기화
    count = 0                                             # 지렁이 수를 0으로 초기화
    for _ in range(k):                                    # 배추 위치를 입력받는 반복문
        x, y = map(int, sys.stdin.readline().split())     # 배추 위치 입력받음
        field[y][x] = 1                                   # 입력받은 위치에 배추 있음을 표시
    for x in range(m):				   # 배열의 가로를 순회
        for y in range(n):             # 배열의 세로를 순회
            if field[y][x] == 1:       # 배추가 있으면
                dfs(x, y)              # 해당 위치에서 DFS를 호출하여 연결된 모든 배추 탐색
                count += 1             # 새로운 배추 발견하면 카운트 증가
    print(count)                       # 배추흰지렁이 마리 수를 출력

 

 

 

 

 

 

 

 

 

 

 

 

[참고]

https://develop247.tistory.com/239

https://f-lab.kr/insight/understanding-dfs-and-bfs-algorithms-20240517