Level 2: PCCP 기출문제 - 석유 시추, BFS 알고리즘

참고 문서

• Programmers: [PCCP 기출문제] 석유 시추

이 문서의 내용

문제 풀이: BFS를 사용한 조각 구성

우선 석유가 위치한 땅을 조각(Fragment)으로 구성합니다. Fragment는 BFS를 사용하여 계산 할 수 있습니다.

• 각 Fragment는 ID를 갖습니다.
• 좌표 x, y를 사용해 Fragment ID를 구할 수 있습니다.
• Fragment ID를 사용해 Fragment의 크기를 구할 수 있습니다.

위 좌표계는 Frament ID를 표현하는 이중 배열 샘플입니다.

석유 시추는 특정 열에 대해서 진행됩니다. 모든 x 좌표에 대해서 각 열이 갖는 Fragment의 크기를 합산하면 결과를 구할 수 있습니다.

이때 하나의 열에서 Fragment ID가 중복되지 않도록 합니다(동일한 Fragment가 합산되지 않도록).

문제를 풀기 위해 BFS를 구현하는 함수를 작성합니다. 이 함수에서는 Fragment ID와 Fragment 크기를 계산합니다.

public void bfs(int[][] land, int x, int y)
{
	Queue<int[]> queue = new LinkedList<>();
	visited[y][x] = true;
	fragmentIds[y][x] = fragmentId;
	queue.add(new int[] { x, y } );
		
	int fragmentSize = 0;
	while (!queue.isEmpty())
	{
		int[] cur = queue.poll();
		++fragmentSize;
		for (int i = 0; i < 4; ++i)
		{
			int cx = cur[0] + dw[i];
			int cy = cur[1] + dy[i];
			if (0 > cx || 0 > cy || w <= cx || h <= cy || true == visited[cy][cx] || 0 == land[cy][cx]) 
				continue;
			visited[cy][cx] = true;
			fragmentIds[cy][cx] = fragmentId;
			queue.add(new int[] { cx, cy });
		}
	}
    
	fragmentSizes.put(fragmentId++, fragmentSize);
}

코드		비고
Line 3:6	visited[y][x]	현재 방문을 좌표계에 마킹합니다.
	fragmentIds[y][x]	현재 Fragment ID를 좌표계에 마킹합니다.
	queue.add(new int[] { x, y })	현재 방문을 BFS 큐에 입력(add)합니다.
Line 11:12	queue.poll() ++fragmentSize	BFS 큐를 꺼내고(poll) Fragment 사이즈를 카운팅합니다.
Line 13:21	for (int i = 0; i < 4; ++i) { }	마지막 방문 좌표를 기준으로 상, 우, 하, 좌 4방향을 검사합니다. 검사된 좌표에 석유가 존재하면 마킹하고 BFS 큐에 입력(add)합니다.
Line 25	put(fragmentId++, fragmentSize)	Fragment ID와 크기를 매핑합니다.

각 좌표 별로 Fragment ID와 Fragment 크기를 알고 있으면 문제를 해결 할 수 있습니다.

각 열에 대한 Fragment 크기의 합을 계산합니다. 전체 코드는 다음과 같습니다.

package com.example.test;

import java.util.*;

class Solution
{
	static int w, h;
	static boolean visited[][];
	static Map<Integer, Integer> fragmentSizes = new HashMap<>();
	static int fragmentIds[][];
	static int fragmentId = 1;
	static int[] dw = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 };
	
	public void bfs(int[][] land, int x, int y)
	{
		Queue<int[]> queue = new LinkedList<>();
		visited[y][x] = true;
		fragmentIds[y][x] = fragmentId;
		queue.add(new int[] { x, y } );
		
		int fragmentSize = 0;
		while (!queue.isEmpty())
		{
			int[] cur = queue.poll();
			++fragmentSize;
			for (int i = 0; i < 4; ++i)
			{
				int cx = cur[0] + dw[i];
				int cy = cur[1] + dy[i];
				if (0 > cx || 0 > cy || w <= cx || h <= cy || true == visited[cy][cx] || 0 == land[cy][cx])
					continue;
				visited[cy][cx] = true;
				fragmentIds[cy][cx] = fragmentId;
				queue.add(new int[] { cx, cy });
			}
		}
		
		fragmentSizes.put(fragmentId++, fragmentSize);
	}
	
	public int solution(int[][] land) {
		w = land[0].length;
		h = land.length;
		visited = new boolean[h][w];
		fragmentIds = new int[h][w];
		
		for (int y = 0; y < h; y++) {
			for (int x = 0; x < w; x++) {
				if (true == visited[y][x] || 0 == land[y][x])
					continue;
				bfs(land, x, y);
			}
		}
		
		int answer = 0;
		for (int x = 0; x < w; ++x) {
			Set<Integer> founds = new HashSet<>();
			for (int y = 0; y < h; ++y) {
				if (0 < fragmentIds[y][x]) {
					founds.add(fragmentIds[y][x]);
				}
			}
			
			int sum = 0;
			for (int fragmentId : founds) {
				sum += fragmentSizes.get(fragmentId);
			}
			
			if (answer < sum)
				answer = sum;
		}
		
		return answer;
	}
}