[백준/1012/Java] 유기농 배추 - BFS 풀이

 

문제

www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

문제를 먼저 풀고 오시는 것을 추천합니다.

이 문제의 풀이는 BFS 외에도 다양한 방법이 있을 수 있으며 제가 보여드리는 풀이는 그 중 하나입니다.

 

 

문제분석

배추흰지렁이는 인접한 다른 배추로 상하좌우 이동할 수 있습니다.

배추가 모여있는 곳은 배추흰지렁이가 한 마리만 있으면 됩니다.

배추가 군데군데 모여있어서 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있습니다.

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)이 주어집니다.

 

출력

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

 

 

풀이

배추 하나에 배추흰지렁이를 살면 방문하지 않은 인접한 배추(상하좌우)로 BFS(너비우선탐색)으로 이동하면 됩니다.

그러나, 밭 전체에 배추가 군데군데 있으므로 방문하지 않은 배추들을 찾아야 합니다.

그래서 밭이 2차원 배열로 되어 있는데 밭 모든 곳을 뒤져야 합니다.

인접한 배추들을 하나의 그룹으로 만들어서 그룹의 개수를 세면 필요한 최소 배추흰지렁이 마리수를 알 수 있습니다.

 

예제풀이

문제에 있는 예제로 풀어보도록 하겠습니다.

 

초기값

배추가 심어져있는 땅을 이렇게 구성되어 있습니다.

가로 10, 세로 6의 크기를 가지고 있는 2차원 배열입니다.

2차원 배열이므로 (0, 0)부터 (9, 5) 위치까지 지렁이가 없는 배추를 검색합니다.

즉, 1이면서 아직 방문하지 않는 배추를 찾습니다.

 

 

 

첫번째 그룹

(0,0)에 배추가 존재하여 여기서부터 시작합니다. 

 

BFS(너비우선탐색)로 상하좌우 이동하여 인접한 배추들을 방문합니다.

오른쪽 배추와 그 아래에 있는 배추를 방문하게 됩니다.

 

두번째 그룹

(0, 0)부터 BFS를 시작하였으니 (0, 1)부터 방문하지 않는 배추를 검색합니다.

그래서 (4, 2) 배추를 찾게 됩니다.

BFS(너비우선탐색)로 상하좌우 이동하여 인접한 배추들을 방문합니다.

바로 아래 배추 1개만 있네요.

 

 

세번째 그룹

그 다음 방문하지 않은 배추를 (5, 2)부터 찾습니다.

그래서 (2, 4) 배추를 찾게 됩니다.

 

BFS(너비우선탐색)로 상하좌우 이동하여 인접한 배추들을 방문합니다.

바로 오른쪽에 배추 1개만 있네요.

 

 

네번째 그룹

그 다음 방문하지 않은 배추를 (3, 4)부터 찾습니다.

그래서 (7, 4) 배추를 찾게 됩니다.

 

BFS(너비우선탐색)로 상하좌우 이동하여 인접한 배추들을 방문합니다.

오른쪽, 아래쪽 부분으로 배추 5개가 인접해있습니다.

 

다섯번째 그룹

그 다음 방문하지 않은 배추를 (8, 4)부터 찾습니다.

이미 방문한 배추들을 제외하고 그 다음 줄에 있는 (8, 5) 배추를 찾게 됩니다.

 

마무리

(9, 5) 위치부터 검색하지만 0 또는 이미 방문한 배추들이어서 모든 2차원 배열을 검색하고 난 후

지금까지 찾은 그룹의 개수인 5를 출력하면 됩니다.

 

 

소스

입력받을 때 M x N 크기의 2차원 배열을 생성하고 배추의 위치가 x, y로 받으므로 해당 위치의 배열값을 1로 변경해주면 됩니다.

그리고 N x M 배열을 모두 돌면서 1(배추)이고 visited (방문) 배열에서 방문하지 않았으면 BFS를 돌립니다.

그 때 그룹 개수를 ANSWER 변수에 저장하였습니다.

모든 검색이 끝난 후 ANSWER 변수를 출력합니다.

 

BFS를 수행할 때 큐에 배추의 위치를 i * 100 + j를 넣고 꺼낼 때 i는 100을 나누고 j는 100의 나머지로 구하는 방식으로 했습니다.

Node 객체를 만들어서 x, y좌표를 저장하고 이를 큐에 넣어서 풀어도 됩니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main
{
	static int M;
	static int N;
	static int K;
	static int arr[][];

	static int visited[][];

	static int list[] = new int[2601];

	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.valueOf(br.readLine());
		for (int tc = 1; tc <= T; tc++)
		{
			int ANSWER = 0;

			StringTokenizer st = new StringTokenizer(br.readLine());
			M = Integer.valueOf(st.nextToken());
			N = Integer.valueOf(st.nextToken());
			K = Integer.valueOf(st.nextToken());

			arr = new int[N][M];
			visited = new int[N][M];

			for (int i = 1; i <= K; i++)
			{
				st = new StringTokenizer(br.readLine());
				int x = Integer.valueOf(st.nextToken());
				int y = Integer.valueOf(st.nextToken());

				arr[y][x] = 1;
			}

			for (int i = 0; i < N; i++)
			{
				for (int j = 0; j < M; j++)
				{
					if (visited[i][j] == 0 && arr[i][j] == 1)
					{
						ANSWER++;
						bfs(i, j);
					}
				}
			}

			System.out.println(ANSWER);

//			for (int i = 0; i < N; i++)
//			{
//				System.out.println(Arrays.toString(visited[i]));
//			}
		}
	}

	private static void bfs(int i, int j)
	{
		Queue<Integer> q = new LinkedList<Integer>();

		q.offer(i * 100 + j);
		visited[i][j] = 1;

		int pos = 0;
		while (q.isEmpty() == false)
		{
			pos = q.poll();
			i = pos / 100;
			j = pos % 100;

			if (i > 0 && arr[i - 1][j] == 1 && visited[i - 1][j] == 0)
			{
				visited[i - 1][j] = 1;
				q.offer((i - 1) * 100 + j); // 상
			}
			if (i < N - 1 && arr[i + 1][j] == 1 && visited[i + 1][j] == 0)
			{
				visited[i + 1][j] = 1;
				q.offer((i + 1) * 100 + j); // 하
			}
			if (j > 0 && arr[i][j - 1] == 1 && visited[i][j - 1] == 0)
			{
				visited[i][j - 1] = 1;
				q.offer(i * 100 + (j - 1)); // 좌
			}
			if (j < M - 1 && arr[i][j + 1] == 1 && visited[i][j + 1] == 0)
			{
				visited[i][j + 1] = 1;
				q.offer(i * 100 + (j + 1)); // 우
			}
		}
	}
}

 

관련글:

2021/02/07 - [Algorithm] - [백준/1260/Java] DFS와 BFS

[백준/1260/Java] DFS와 BFS

 

2021/01/29 - [Algorithm] - [백준/2178/Java] 미로탐색 - BFS 풀이

[백준/2178/Java] 미로탐색 - BFS 풀이