문제

https://school.programmers.co.kr/learn/courses/30/lessons/250136

---

입력

• 석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land가 매개변수로 주어집니다.

---

출력

• 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 return

---

풀이

제한조건

• 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 500
• 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 500
• land[i][j]는 i+1행 j+1열 땅의 정보를 나타냅니다.
• land[i][j]는 0 또는 1입니다.
• land[i][j]가 0이면 빈 땅을, 1이면 석유가 있는 땅을 의미합니다.

접근방법

BFS
BFS를 이용한 탐색으로 해결할 수 있다.
(DFS로 접근해 보았으나, 함수 스택의 문제인지 효율성 체크 부분에서 런타임 에러가 발생했다.)
효율성 체크가 존재하는 만큼 탐색을 최소화할 방법을 찾아야한다.
아이디어를 먼저 떠올려보자.

1. 탐색을 통해 석유 덩어리를 찾는다.
2. 각 덩어리의 크기도 구한다.
3. 각 열에서 접근할 수 있는 석유 덩어리가 어떤것이 있는지 찾는다.

1. 탐색을 통해 석유 덩어리를 찾는다.
전체 좌표를 순회하며

• 탐색한 적이 없고
• 해당 위치가 석유
  라면 탐색을 시작한다.

해당 위치에서 인접한 구역에 석유가 있다면, 같은 석유 덩어리다.
따라서 visit 배열에 같은 그룹 아이디로 표시한다.

2. 각 덩어리의 크기도 구한다.
1번 과정을 수행하는 과정에서 인접한 구역을 찾을 때 마다 카운팅을 해주자.
그럼 탐색이 종료되었을때, 해당 덩어리의 크기를 구할 수 있다.

여기서 몇 개의 석유 덩어리가 발견될 지 아직은 알 수 없다.
따라서 Map자료 구조를 이용해서 기록해두자.

Map<Integer, Integer> map = new HashMap<>(); // <그룹ID, 갯수>

3. 각 열에서 접근할 수 있는 석유 덩어리가 어떤것이 있는지 찾는다.
이제 각 열을 중심으로 최대값을 갱신을 시도해보자.
각 열에 대해서 모든행에 대해 찾아보자.
중복해서 같은 그룹이 나올 수 도 있기때문에 Set자료구조를 이용해서 중복을 처리하자.

int answer = 0;
for (int j = 0; j < M; ++j) {
	Set<Integer> set = new HashSet<>();
    // 각 열에서 접근 가능한 그룹을 찾는다
    for (int i = 0; i < N; ++i) {
    if (visit[i][j] != 0)
    	set.add(visit[i][j]);
    }
    int sum = 0;
    // 접근 가능한 모든 그룹의 크기의 합을 구한다.
    for (int value : set) {
    	sum += map.get(value);
    }
    answer = Math.max(answer, sum);
}

---

코드

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class Solution {
	int N, M;
	int[][] visit, arr;
	int[] dx = {-1, 0, 1, 0};
	int[] dy = {0, 1, 0, -1};
	Map<Integer, Integer> map = new HashMap<>();

	public int solution(int[][] land) {
		N = land.length;
		M = land[0].length;
		visit = new int[N][M];
		arr = land;

		int groupId = 0;
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < M; ++j) {
				if (arr[i][j] == 1 && visit[i][j] == 0) {
					groupId++;
					search(i, j, groupId);
				}
			}
		}

		int answer = 0;
		for (int j = 0; j < M; ++j) {
			Set<Integer> set = new HashSet<>();
			for (int i = 0; i < N; ++i) {
				if (visit[i][j] != 0)
					set.add(visit[i][j]);
			}
			int sum = 0;
			for (int value : set) {
				sum += map.get(value);
			}
			answer = Math.max(answer, sum);
		}

		return answer;
	}

	private void search(int x, int y, int groupId) {
		visit[x][y] = groupId;

		Queue<int[]> q = new ArrayDeque<>();
		q.add(new int[] {x, y});

		int count = 1;
		while (!q.isEmpty()) {
			int[] pos = q.poll();
			for (int d = 0; d < 4; ++d) {
				int nx = pos[0] + dx[d];
				int ny = pos[1] + dy[d];
				if (!isInRange(nx, ny)) // 범위 밖은 탐색하지 않는다.
					continue;
				if (visit[nx][ny] != 0) // 이미 탐색된 부분은 탐색하지 않는다.
					continue;
				if (arr[x][y] != arr[nx][ny]) // 석유가 없는 자리는 탐색하지 않는다.
					continue;
				visit[nx][ny] = groupId;
				q.add(new int[] {nx, ny});
				count++;
			}
		}
		map.put(groupId, count);
	}

	public boolean isInRange(int x, int y) {
		if (0 <= x && x < N && 0 <= y && y < M)
			return true;
		return false;
	}
}