백준_1012_유기농배추

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

1012번: 유기농 배추

 

문제요약)

어떤 배추에 흰 지렁이가 살고 있으면 상하좌우 네 방향에 위치한 배추를 보호한다.

배추를 군데군데 심어 놓았는데 서로 인접해있는 배추들이 몇 군데 퍼져있는지 조사하면 총 몇마리의 지렁이가 필요한 지 알 수 있다.

0은 배추가 심어져 있지 않고 1은 배추가 심어져있음을 나타낸다.

배추밭이 그림과 같이 구성되어 있으면 최소 5마리의 배추흰시렁이가 필요하다.

 

 

 

 

 

입력)

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

 

출력)

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

 

풀이포인트)

백준_2667_단지번호  풀이와 동일한 방법으로 풀이가 가능하다. 

백준_2667_단지번호붙이기

1이 인접한 칸들(상하좌우)을 연결해 한 구역으로 가정하고 구역당 지렁이 1마리가 필요하다.

1인 칸을 발견하면 BFS수행 후 0으로 방문처리하고 1을 카운트 해준다.

 

풀이)

from collections import deque #collections에서 deque불러오기

#상하좌우로 이동할 좌표
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

t = int(input()) #입력 받을 테스트 케이스 수

#bfs전 처리
for i in range(t): #테스트 케이스만큼 반복
	count = 0 #지렁이 수 초기화
    n, m, k = map(int, input().split()) #지도의 가로, 세로 길이, 배추의 위치의 개수
    graph = [[0] * m for _ in range(n)] #입력받은 지도의 길이 범위 내에서 지도 그리기
    
    for j in range(k): #배추 위치의 개수 범위만큼 반복
    	x, y = map(int, input().split()) #배추의 위치 입력받기
        graph[x][y] = 1 #배추의 위치에 1 입력하기

#bfs
def bfs(graph, a, b) #매개변수가 graph, a, b인 bfs 함수
	queue = deque() #queue를 deque로 선언
    queue.append((a, b) #a, b를 queue에 삽입
    graph[a][b] = 0 #그래프 표현
    
    while queue: #queue 내에 아무것도 안남을 때 까지 반복
    x, y =queue.popleft() #queue에서 popleft한 x, y
    for i in range(4) #현재위치에서 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 #재방문 방지를 위해 방문처리 0
            queue.append((nx, ny)) #queue에 신규위치 추가
    return
    
      
for a in range(n): #배추 받 세로길이 범위
    	for b in range(m): #배추 밭 가로길이 범위
        	if graph[a][b] == 1: #배추가 있다고 하면
            	bfs(graph, a, b) #bfs 실행
                count += 1 #지렁이 +1 카운트
                
print(count) #지렁이 수 출력