BFS

프로그래머스 PCCP 기출문제 2번을 풀어보았다. 문제 제목이 없지만 이름을 짓자면 석유 시추 라고 할 수 있을 것 같다.
문제 링크는 다음과 같다.
https://school.programmers.co.kr/learn/courses/30/lessons/250136

---

조각별로 정보 초기화

석유가 있는 곳들 중 서로 연결된 부분들을 하나의 조각으로 본다고 약속하자. 이는 fragment란 이름의 변수로 사용할 것이다. fragment의 정보들을 적절히 초기화해주는 것이 중요하다.

각 칼럼별로 몇개의 조각을 품게 될지 알기 위해서 조각들별로 번호를 붙여주는 것이 중요하다. 하나의 칼럼이 같은 조각에 해당하는 칸을 여러 칸 품고 있더라도 하나의 조각으로 계산해야 하기 때문이다. 이 부분이 풀이의 핵심인 것 같다.

조각 정보들 초기화

먼저 주어진 land를 순회하며 (1) 몇개의 조각이 존재하는지 + (2) 각 조각의 사이즈는 몇인지 를 알아보아야 한다. 이는 BFS로 해결했다. 석유가 있는 칸을 발견하면 그 칸을 시작점으로 설정하고, 연결된 모든 칸들을 Queue에 집어넣으며 삽입된 모든 칸들의 사이즈를 순차적으로 갱신하며 각 칸별로 조각 번호를 부여했다.
다음은 이 작업에 대한 코드다.

static int[][] fragments; // 각 칸이 몇 번 조각에 속해있는지 알려줄 배열
static int fragmentIdx = 1; // 조각별 번호. 시작은 1번부터
static Map<Integer, Integer> fragmentsInfo = new HashMap<>(); // 각 조각별 size 정보 담을 Map
static boolean[][] visited; // 방문 정보

static void initFragment(int[][] land, int r, int c) {
	visited[r][c] = true;
	fragments[r][c] = fragmentIdx;
	Queue<int[]> q = new LinkedList<>();
	q.add(new int[]{r, c});
	int size = 0;

	while (!q.isEmpty()) {
		int[] cur = q.poll();
		size++; // 새로운 칸이 들어올 때마다 사이즈 증가

		for (int d = 0; d < 4; d++) {
			int nxtR = cur[0] + dirR[d];
			int nxtC = cur[1] + dirC[d];

            if (nxtR < 0 || nxtR >= rSize || nxtC < 0 || nxtC >= cSize || visited[nxtR][nxtC] || land[nxtR][nxtC] == 0) {
				continue;
            }

            visited[nxtR][nxtC] = true;
            fragments[nxtR][nxtC] = fragmentIdx; // 새로운 칸은 몇번 조각에 해당하는지 갱신
            q.add(new int[]{nxtR, nxtC});
		}
	}

	fragmentsInfo.put(fragmentIdx++, size); // 모든 조각을 다 처리하고 나서 조각의 size 갱신
}

칼럼별로 어떤 조각들을 품고 있는지

결국 문제가 묻고있는 것은 각 칼럼별로 품고 있는 조각들의 total size가 얼마냐는 것이다. 이를 위해 특정 칼럼의 모든 열을 돌며 몇 번 조각들을 품고 있는지, 조각 번호를 Set에 담아둠으로써 알아낼 수 있다.
이렇게 알아낸 조각들이 각각 얼마의 size인지 모두 더해주면 하나의 칼럼별로 시추할 수 있는 석유의 총량을 구할 수 있다. 각 조각별 size는 앞선 과정에서 업데이트해둔 fragmentInfo를 통해 가져올 수 있다.
이를 코드로 나타내면 다음과 같다.

for (int c = 0; c < cSize; c++) {
	Set<Integer> fragmentTypes = new HashSet<>();
	int tmpMaxAmount = 0;
	for (int r = 0; r < rSize; r++) {
		if (fragments[r][c] > 0) {
			fragmentTypes.add(fragments[r][c]);
		}
	}

	for (Integer frg : fragmentTypes) {
		tmpMaxAmount += fragmentsInfo.get(frg);
	}

	answer = Math.max(answer, tmpMaxAmount);
}

---

전체 코드

위의 모든 과정들을 모두 합친 내 코드는 다음과 같다.

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

public class PCCP2번 {

    static int rSize, cSize;
    static int[][] fragments;
    static int fragmentIdx = 1;
    static Map<Integer, Integer> fragmentsInfo = new HashMap<>();
    static boolean[][] visited;
    static int[] dirR = {-1, 1, 0, 0};
    static int[] dirC = {0, 0, -1, 1};

    public int solution(int[][] land) {
        int answer = 0;
        rSize = land.length;
        cSize = land[0].length;
        fragments = new int[rSize][cSize];
        visited = new boolean[rSize][cSize];

        for (int r = 0; r < rSize; r++) {
            for (int c = 0; c < cSize; c++) {
                if (visited[r][c] || land[r][c] == 0) {
                    continue;
                }

                initFragment(land, r, c);
            }
        }

        for (int c = 0; c < cSize; c++) {
            Set<Integer> fragmentTypes = new HashSet<>();
            int tmpMaxAmount = 0;
            for (int r = 0; r < rSize; r++) {
                if (fragments[r][c] > 0) {
                    fragmentTypes.add(fragments[r][c]);
                }
            }

            for (Integer frg : fragmentTypes) {
                tmpMaxAmount += fragmentsInfo.get(frg);
            }

            answer = Math.max(answer, tmpMaxAmount);
        }

        return answer;
    }

    static void initFragment(int[][] land, int r, int c) {
        visited[r][c] = true;
        fragments[r][c] = fragmentIdx;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{r, c});
        int size = 0;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            size++;

            for (int d = 0; d < 4; d++) {
                int nxtR = cur[0] + dirR[d];
                int nxtC = cur[1] + dirC[d];

                if (nxtR < 0 || nxtR >= rSize || nxtC < 0 || nxtC >= cSize || visited[nxtR][nxtC]
                        || land[nxtR][nxtC] == 0) {
                    continue;
                }

                visited[nxtR][nxtC] = true;
                fragments[nxtR][nxtC] = fragmentIdx;
                q.add(new int[]{nxtR, nxtC});
            }
        }

        fragmentsInfo.put(fragmentIdx++, size);
    }
}